Congruence of IntegersDate: 08/10/98 at 18:20:07 From: Irene Subject: Congruence of integers (modulus) Hi Dr. Math. Here are a few questions that I am really confused on: 1. Translate these statements into the language of congruences: a. The sum of two even integers is even. b. The sum of an even integer and an odd integer is odd. c. 3 divides 12. 2. Find the remainder when 5 to the power of 1001 is divided by 6. 3. Give three solutions in natural numbers to each of these congruences: x is congruent 1 mod 2, 3x is congruent to 2 mod 5. It says: Exercises 25-32 develop simple divisibility tests for some small divisors. 25. Use the fact that 10 is congruent to 0 mod 2 to obtain the following test for divisibility by 2 -- a number is divisible by 2 if its units digit is divisible by 2. Using the above, prove that a number is divisible by 6 if its last digit is even and the sum of its digits is divisible by 3. 32. How would you test for divisibility by 12? 52. If the product of two numbers is 0, then at least one of them is O. Is this true in the mod 5 arithmetic? 53. In the mod 5 arithmetic, find 2/3. That is, solve the equation 3x = 2. Show that 3 has no square root (that is, show that there is no x such that x^2 = 3. Thank you so much for your help. It is greatly appreciated. Date: 08/11/98 at 13:12:40 From: Doctor Anthony Subject: Re: congruence of integers (modulus) In the problems below, I shall use the symbol '=' to mean 'congruent'. Problem 1: The sum of two even integers is even translates to: If a and b are even a+b = 0 (mod 2) The sum of an even integer and an odd integer is odd translates to: If a is even and b is odd a+b = 1 (mod 2) 3 divides 12 translates to: 12 = 0 (mod 3) Problem 2: Find the remainder when 5 to the power of 1001 is divided by 6. 5 = 5 (mod 6) 5^2 = 1 (mod 6) 5^3 = 5 (mod 6) 5^4 = 1 (mod 6) 5^5 = 5 (mod 6) We see that for even powers of 5 the remainder is always 1 and for odd powers of 5 the remainder is always 5. Thus 5^1001 = 5 (mod 6). So the remainder is 5. Problem 3: If x = 1 (mod 2), then x could equal 3, 5, 7, ..... If 3x is congruent to 2 mod 5, then: 3x = 2 (mod 5) = 7 (mod 5) = 12 (mod 5) so x = 4 is one solution = 17 (mod 5) = 22 (mod 5) = 27 (mod 5) so x = 9 is another solution Similarly, (3)(14) = 42 = 2 (mod 5), so x = 14 is another solution. For problem 25: I'll show that a number is divisible by 2 if its units digit is divisible by 2 for a two-digit number. A number ab, where a and b are digits 0 through 9, can be written as 10a + b. So using the fact that 10 = 0 (mod 2), 10a + b = 0 (mod 2) if and only if b = 0 (mod 2). Using the fact that 10^k = 0 (mod 2) for any k, the above method can be used to show that any number is divisible by 2 if its units digit is divisible by 2. A number is divisible by 6 if it is divisible by 2 (last digit is even) and if it is divisible by 3. I've already shown the condition necessary for the number to be divisible by 2. I'll prove that if the sum of the digits of a number is divisible by three then the number is divisible by 3 for a three-digit number. A number abc means 100a + 10b + c. So: 100a + 10b + c = (99+1)a + (9+1)b + c = 99a + 9b + (a+b+c) = 0 (mod 3) if and only if a+b+c = 0 (mod 3) Again, this can be generalized for a number with any arbitrary number of digits. So a number is divisible by 6 if it is even and the sum of the digits is divisible by 3. Problem 32: To test for divisibility by 12, test for divisibility by 3 and by 4. We have given the test for divisibility by 3. The test for divisibility by 4 is if last two digits are divisible by 4. Using abc = 100a + 10b + c, since 100a = 0 (mod 4), we require 10b + c = 0 (mod 4). Problem 52: Since 2 x 5 = 10 = 0 (mod 5), it is not true in mod 5 arithmetic if you consider 5 as a number in its own right. In some cases, since 5 = 0 (mod 5), 5 may not be considered different from 0. Problem 53: In question 3 we showed that 3x = 2 mod (5) has solutions 4, 9, 14, .... So x = 2/3 (mod 5) has the same solutions. Now, we must show that x^2 = 3 (mod 5) has no solutions. Suppose that there does exist an x such that x^2 = 3 (mod 5). Then we require 3, 8, 13, 18, 23, 28, 33, 38, 43, ... to be a perfect square. We could write this as: x^2 = -2 (mod 5) x^2 + 2 = 0 (mod 5) Now the final digit of the sequence 1^2, 2^2, 3^2, ... goes 1, 4, 9, 6, 5, 6, 9, 4, 1, 0, and then repeats this sequence for ever more. Adding 2 to the sequence, we get: 3, 6, 11, 8, 7, 8, 1, 6, 3, 2, .... It follows that x^2 + 2 can never end in 0 or 5 and so there is no solution to x^2 + 2 = 0 (mod 5). Thus there is so no solution to x^2 = 3 (mod 5). Information on divisibility rules can also be found in the Dr. Math FAQ: http://mathforum.org/dr.math/faq/faq.divisibility.html - Doctor Anthony and Sarah, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/