Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Discrete Mathematics
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search