Mathematics
Divisibility Tests
Divisibility tests are rules that help determine whether a number is divisible by another number without performing the actual division. These tests are based on the properties of numbers and can be used to quickly check divisibility by 2, 3, 4, 5, 6, 8, 9, and 10.
Written by Perlego with AI-assistance
Related key terms
1 of 5
10 Key excerpts on "Divisibility Tests"
Available until 1 Jan |Learn more- Sergei Abramovich(Author)
- 2006(Publication Date)
- Information Age Publishing(Publisher)
Sometimes, carrying out divisions is not necessary. Instead, the so-called tests of divisibility can be used. Some such tests are not difficult, yet some tests are very complicated, and, in the age of computing technology, have little practical value. In the next section, the most commonly known and easily applicable tests of divis- ibility by 2, 3, 5, 9, and 11 will be discussed. 4. Divisibility Tests What does it mean for a number to divide another number? To answer this question, consider two models for division—partition model and measurement model—that can be introduced through the following two problems. Problem 1 (Partition Model for Division): Andy had ten marbles. He put them evenly in two boxes. How many marbles are in each box? Problem 2 (Measurement Model for Division): Andy had ten marbles. He put them in boxes designed for five marbles each. How many boxes did he need? 98 Topics in Mathematics for Elementary Teachers Figure 6.3 represents a solution for each of the two problems. Yet, the answer for each problem is different. For Problem 1, the answer is five marbles; for Problem 2, the answer is two boxes. We solved Problem 1 by dividing two into ten using the partition model, something that conceptual- izes division as fair sharing. We solved Problem 2 by dividing five into ten using the measurement model, something that conceptualizes division as repeated subtraction. One can see that the partition model with respect to divisibility of ten by two is equivalent to the measurement model with respect to divisibility of ten by five. By the same token, as shown in Figure 6.4, the partition model with re- spect to divisibility of ten by five (arranging ten marbles in five groups) is equivalent to the measurement model with respect to divisibility of ten by two (arranging ten marbles in groups of two).
- Xiaoyun Wang, Guangwu Xu, Mingqiang Wang, Xianmeng Meng(Authors)
- 2015(Publication Date)
- CRC Press(Publisher)
C H A P T E R 1 Divisibility of Integers D ivisibility is a key concept in number theory. The main purpose of this chapter is to introduce some basic concepts and prop-erties that relate to divisibility. Some of them, such as divisibility, divisors, common divisors, the least common multiples, and factoriza-tion, have already been taught in middle school and high school. Here we shall define them by a precise mathematical language. Through mas-tering mathematical definitions and properties of these concepts, we can further solve many elementary number theoretic problems related to divisibility. The theory of divisibility has a rich content and pro-vides flexible problem-solving methods. It not only is the foundation of number theory and algebra, but also has a wider range of applications to cryptography. Some important applications in cryptography include prime factorization of integers, and the Euclidean algorithm for finding greatest common divisors. 1.1 THE CONCEPT OF DIVISIBILITY We use Z to denote the set of all integers and N the set of all natural numbers. The definition of divisibility is as follows: Definition 1.1 Let a, b ∈ Z . If there is a q ∈ Z , such that b = aq , then b is said to be divisible by a and denoted as a | b ; b is called a multiple of a , and a is called a divisor (or a factor) of b . Otherwise, b is said to be not divisible by a , or a does not divide b , denoted by a b . By this definition and the law of operation, the following properties of divisibility are immediate: 1 2 Mathematical Foundations of Public Key Cryptography Theorem 1.2 Let a, b, c ∈ Z . Then 1. a | b and b | c ⇒ a | c . 2. a | b and a | c ⇔ for all x, y ∈ Z , a | bx + cy . 3. If m ∈ Z and m = 0 , then a | b ⇔ ma | mb . 4. a | b and b | a ⇒ a = ± b . 5. If b = 0 , then a | b ⇒ | a | ≤ | b | . Proof 1. Since a | b , by the definition of divisibility, there is a q 1 such that b = aq 1 .
eBook - PDFMathematical Practices, Mathematics for Teachers
Activities, Models, and Real-Life Examples
- Ron Larson, Robyn Silbey(Authors)
- 2014(Publication Date)
- Cengage Learning EMEA(Publisher)
5.1 Divisibility Tests 5.2 Primes and Composites 5.3 Greatest Common Factor and Least Common Multiple Number Theory 5 iStockphoto.com/digitalskillet 159 Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 160 Chapter 5 Number Theory Materials: • Pencil Learning Objective: Decide whether given whole numbers are divisible by 2, 3, 4, 5, and 10. Then describe a divisibility test for each of the numbers 2, 3, 4, 5, and 10. Name _____________________________ 1. Divisibility by 2 Circle each whole number that is evenly divisible by 2. 6 13 14 18 25 32 50 77 Write a rule that tells you when a whole number is evenly divisible by 2. 2. Divisibility by 5 Circle each whole number that is evenly divisible by 5. 15 18 30 36 45 74 75 90 Write a rule that tells you when a whole number is evenly divisible by 5. 3. Divisibility by 10 Circle each whole number that is evenly divisible by 10. 15 18 30 36 45 74 75 90 Write a rule that tells you when a whole number is evenly divisible by 10. 4. Divisibility by 4 Circle each whole number that is evenly divisible by 4. 13 24 30 76 148 220 504 618 Write a rule that tells you when a whole number is evenly divisible by 4. 5. Divisibility by 3 Circle each whole number that is evenly divisible by 3. 6 18 26 27 30 44 58 72 Write a rule that tells you when a whole number is evenly divisible by 3. Activity: Describing Divisibility Rules Pressmaster/Shutterstock.com Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.
eBook - PDFMathematics for Elementary Teachers
A Contemporary Approach
- Gary L. Musser, Blake E. Peterson, William F. Burger(Authors)
- 2013(Publication Date)
- Wiley(Publisher)
On the other hand, the solution is immediate for one who understands the concept of divisibility of numbers. Initial Problem A major fast-food chain held a contest to promote sales. With each purchase a cus- tomer was given a card with a whole number less than 100 on it. A $100 prize was given to any person who presented cards whose numbers totaled 100. The following are several typical cards. Can you find a winning combination? 3 9 12 15 18 27 51 72 84 Can you suggest how the contest could be structured so that there would be at most 1000 winners throughout the country? (Hint: What whole number divides evenly in each sum?) Clues The Use Properties of Numbers strategy may be appropriate when Special types of numbers, such as odds, evens, primes, and so on, are involved. A problem can be simplified by using certain properties. A problem involves lots of computation. A solution of this Initial Problem is on page 202. Use Properties of Numbers Problem-Solving Strategies 1. Guess and Test 2. Draw a Picture 3. Use a Variable 4. Look for a Pattern 5. Make a List 6. Solve a Simpler Problem 7. Draw a Diagram 8. Use Direct Reasoning 9. Use Indirect Reasoning 10. Use Properties of Numbers 176 AUTHOR WALK-THROUGH INTRODUCTION Number theory is a branch of mathematics that is devoted primarily to the study of the set of counting numbers. The aspects of the counting numbers central to the elementary curriculum that are covered in this chapter include primes, composites, and Divisibility Tests as well as the notions of greatest com- mon factor and least common multiple. Many of these topics are useful in other areas of mathematics such as fractions (Chapter 6) and algebra. Being able to find common factors and greatest common factors between pairs of numbers is useful when simplifying fractions. Understanding least common multiples is useful for finding a common denominator when adding and subtracting fractions.
eBook - PDFNumber, Shape, & Symmetry
An Introduction to Number Theory, Geometry, and Group Theory
- Diane L. Herrmann, Paul J. Sally Jr.(Authors)
- 2012(Publication Date)
- A K Peters/CRC Press(Publisher)
. . . . . 3 Divisibility and Primes One of the earliest concepts that comes up when people discuss numbers is the idea of a prime number. Usually, if students are asked to describe what a prime number is, the definition comes out as: “A prime is a number that can only be divided by itself and 1.” Since this will be an important definition, let’s take some time to be sure the formal definition is completely precise. In fact, before we can define a prime number, we have to decide what we mean by “divided by.” 3.1 Divisibility When we first talk about division in the integers, we usually mean “divides evenly.” That means we can divide a number into several equal parts with nothing left over. For example, we can agree that 7 divides 21, but does not divide 23. Definition. Start with two integers a and b . We say that a divides b if there is an integer k so that ak = b . We will write this as a | b . Example. We claimed 7 divides 21. How does this fit the definition? Here, a = 7 and b = 21 . What is the integer k for the definition? Simple arithmetic shows that if k = 3, then 7 · 3 = 21. Also, since we cannot find an integer k so that 7 k = 23, we can say that 7 does not divide 23. Example. What about 0? In order for 0 | n to be true, we would need an integer k so that 0 · k = n . Since 0 · k is 0 for every possible k , the only integer that 0 divides is 0 itself. Practice Problem 3.1. Which integers divide 0 ? 67 68 3 . Divisibility and Primes If a divides b , we call a a factor , or a divisor , of b . What are the other factors of 21? From elementary arithmetic, we would come up with a short list of the numbers 1, 3, 7, and 21. These are all the positive divisors of 21. Are there any negative divisors? Yes, in fact, -1, -3, -7, and -21 are also divisors of 21. Let’s check one of them. Example. Let’s show that -3 divides 21. Here, a = -3 and b = 21. What integer k makes the equation -3 k = 21 true? If k = -7, we know that ( -3)( -7) = 21 .
eBook - PDFA Discrete Transition to Advanced Mathematics
Second Edition
- Bettina Richmond, Thomas Richmond(Authors)
- 2023(Publication Date)
- American Mathematical Society(Publisher)
First, the tests may be applied repeatedly in a single problem. For example, the test for divisibility by 3 tells us that the number 58,976,948 is divisible by 3 if and only if 5+8+9+7+6+9+4+8 = 56 is divisible by 3. Furthermore, 56 is divisible by 3 if and only if 5 + 6 = 11 is, and 11 is divisible by 3 if and only if 1 + 1 = 2 is. Thus 58,976,948 is divisible by 3 if and only if 2 is. Since 2 is not divisible by 3, neither is 58,976,948. Finally, the Divisibility Tests provide information on remainders. For example, 4938 is not a multiple of 9 since 4 + 9 + 3 + 8 = 24 is not; 24 is 6 more than a multiple of 9. Decreasing the units digit of 4938 by 6 will have the same effect on the sum of the digits of 4938 since the subtraction occurs entirely among the units digits, with no “borrowing” necessary. Thus, both 4938 and the sum of its digits are 6 more than a multiple of 9 and therefore have the same remainder when divided by 9. Now consider 4983. Again the sum of its digits is 24, which is 6 more than a multiple of 9. Decreasing 4983 by 6 does not have the same effect on the sum of the digits since the subtraction would involve borrowing from the tens digit. (Indeed, decreasing 4983 by 6 gives a number for which the sum of the digits has increased from 24.) However, the sum of the digits of 4938 is 3 less than a multiple of 9, and adding 3 to 4983 will have the same effect upon the sum of the digits because this arithmetic occurs entirely among the units digits, with no “carrying” involved. Now since 4983 and 24 = 4 + 9 + 8 + 3 are both 3 less than a multiple of 9, they have the same remainder when divided by 9. Given any number, one of these two techniques will apply. Thus, the remainder when is divided by 9 (respectively, 3) equals the remainder when the sum of the digits of 3.4. Divisibility Tests 121 is divided by 9 (respectively, 3).
eBook - PDF- C Y Hsiung(Author)
- 1992(Publication Date)
- WSPC(Publisher)
Chapter 1. THEORY OF DIVISIBILITY The aim of the Elementary Theory of Numbers is to investigate the properties of integers. Most of them are related to divisibility which is the foundation of the theory. Thus, first of all we study the basic theory of divisibility in this chapter. 1.1. Divisibility We have known that by integers we mean . . . , — 2 , -1 , 0 , 1 , 2,... , and by positive integers or natural numbers we mean 1,2... . The sum, difference and product of two integers are obviously inte-gers. But the quotient of two integers may or may not be an integer; it is an integer only in special cases. If an integer b (^ 0) divides an integer a, that is, a/b = c, an integer, then a = 6c, we say that a is a multiple of 6, and b is a divisor or factor of a. We use ba to denote that b divides a, while bl a to denote that b does not divide a. Clearly, l|a, and if b ^ 0, then 6|0,6|6. Moreover, if b > 1, then bj( 1, that is, 1 is a divisor of any integer, and 0 is a multiple of any integer. Any nonzero integer is a divisor or a multiple of itself. l 2 Elementary Theory of Numbers A number which is a multiple of 2 is called an even number, otherwise it is called an odd number. If a = qb and q j£ ± l , ± a , then b is called a proper divisor or factor of a. It is easily seen that the square of an odd number 2k + 1 is of the form 8A: + 1, and the square of any even number 2k is of the form 4k. Since the absolute value of a divisor of a nonzero number is not greater than the absolute value of that number itself, the number of divisors of any nonzero number is only finite. The following theorem is an immediate consequence of this defi-nition. Theorem 1. Let b / 0,c ^ 0. 1. If c|6,6|a, then c|a. 2. If fc|a, then cbca. 3. If c|a,c|6, then c(ma + n&), where m and n are any integers.
Available until 4 Dec |Learn more- James S. Kraft, Lawrence C. Washington(Authors)
- 2016(Publication Date)
- Chapman and Hall/CRC(Publisher)
Chapter 1 Divisibility 1.1 Divisibility A large portion of this book will be spent studying properties of the integers. You can add, subtract and multiply integers and doing so always gives you another integer. Division is a little trickier. Sometimes when you divide one integer by another you get an integer (12 divided by 3) and sometimes you don’t (12 divided by 5). Because of this, the first idea we have to make precise is that of divisibility. Definition 1.1. Given two integers a and d with d non-zero, we say that d divides a (written d | a ) if there is an integer c with a = cd . If no such integer exists, so d does not divide a , we write d -a . If d divides a , we say that d is a divisor of a . Examples. 5 | 30 since 30 = 5 · 6, and 3 | 102 since 102 = 3 · 34, but 6 -23 and 4 --3. Also, -7 | 35, 8 | 8, 3 | 0, -2 | -10, and 1 | 4. Remark. There are two technical points that need to be men-tioned. First, we never consider 0 to be a divisor of anything. Of course, we could agree that 0 | 0, but it’s easiest to avoid this case completely since we never need it. Second, if d is a divisor of a , then -d is a divisor of a . However, whenever we talk about the set of divisors of a positive integer, we follow the convention that we mean the positive divisors. So we say that the divisors of 6 are 1, 2, 3, and 6 (and ignore -1, -2, -3, -6). There are several basic results concerning divisibility that we will be using throughout this book. 9 10 Chapter 1 Divisibility Proposition 1.2. 1 Assume that a , b , and c are integers. If a | b and b | c , then a | c . Proof. Since a | b , we can write b = ea and since b | c , we can write c = fb with e and f integers. Then, c = fb = f ( ea ) = ( fe ) a . So, by definition, a | c . Example. The proposition implies, for example, that a multiple of 6 is even: Let a = 2 and b = 6, and let c be an arbitrary integer. Then a | b . If 6 | c , the proposition says that 2 | c , which says that c is even.
eBook - PDF- Richard A. Mollin(Author)
- 2006(Publication Date)
- Chapman and Hall/CRC(Publisher)
Chapter 1 Mathematical Basics In this introductory chapter, we set up the basics for number theoretic con-cepts in the first seven sections and the basics for complexity in the last section. This will provide us with the foundations to study the cryptographic notions later in the book. Indeed, this material, together with Appendices A–B, com-prise all the requisite background material in number theory and algorithmic complexity needed throughout the text. 1.1 Divisibility For background on notation, sets, number systems, and other fundamental facts, the reader should consult Appendix A. Definition 1.1 Division If a, b ∈ Z , b = 0 , then to say that b divides a , denoted by b | a , means that a = bx for a unique x ∈ Z , denoted by x = a/b . Note that the existence and uniqueness of x implies that b cannot be 0 . We also say that a is divisible by b . If b does not divide a , then we write b a and say that a is not divisible by b . We say that division by zero is undefined . We may classify integers according to whether they are divisible by 2, as follows. Definition 1.2 Parity If a ∈ Z , and a/ 2 ∈ Z , then we say that a is an even integer . In other words, an even integer is one which is divisible by 2 . If a/ 2 ∈ Z , then we say that a is an odd integer. In other words, an odd integer is one which is not divisible by 2 . If two integers are either both even or both odd, then they are said to have the same parity . Otherwise they are said to have opposite or different parity . 1 2 1. Mathematical Basics In order to prove our first result, we need a concept that will be valuable throughout. Definition 1.3 The Floor Function If x ∈ R , then there is a unique integer n such that n ≤ x < n + 1 . We say that n is the greatest integer less than or equal to x , sometimes called the floor of x , denoted by x = n . The reader may test understanding of the floor function by solving Exercises 1.12–1.19 on pages 4–5.
eBook - ePub- W. W. Sawyer(Author)
- 2012(Publication Date)
- Dover Publications(Publisher)
CHAPTER TWODivisibility
IN Chapter 1 we saw that 53,312 could not possibly equal 127 x 419, since 53,312 is an even number while 127 × 419 must be odd. This simple statement illustrates two ways in which the chaos of large numbers has become organized. The first way lies in the writing of the numbers themselves. If we were shown two heaps of stones, one containing 127, the other 128 stones, we could not tell which was which. But we distinguish with ease the written numbers 127 and 128. The second way in which organization has come is shown by the fact that we immediately recognize 53,312 as being an even number. This we certainly could not do if we had 53,312 actual objects before our eyes, lying in a disorderly heap. This chapter is concerned with these two themes - the writing of numbers and tests for divisibility. For when we recognize that a number is even, we are saying that it is divisible by 2. There are also ways of deciding quickly whether a number is divisible by 9, by 3, by 5, by 4, or by 8; if it is not exactly divisible, the remainder can be stated. The test for divisibility by 9 is often justified in algebra books. My impression is that many pupils learn to reproduce this proof without ever understanding it properly. This test, however, can be justified without any use of algebra by direct vision, and this we shall do. Further, the method used is applicable to the other numbers, 2, 4, 8, 5, 3, and even to 7. It is often said that there is no quick way of testing for divisibility by 7. In a way this is true. While our approach will give us a test for 7, it is certainly not a test of any practical value. However, it has some interest, not least the fact that the learner can develop it for himself.THE WRITING OF NUMBERS
In Chapter 4 of Mark Twain’s Tom Sawyer
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
