Congruence of Integers

Date: 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/