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

### Using Modular Arithmetic to Test Divisibility of Large Numbers

```Date: 08/30/2008 at 06:32:55
From: Judy
Subject: Divisibility of big numbers

Prove that 55^62 - 2*13^62 + 41^62 is divisible by 182.

I don't know how to go about it at all. I have no idea where to start.

```

```
Date: 08/30/2008 at 13:46:43
From: Doctor Greenie
Subject: Re: Divisibility of big numbers

Hi, Judy -

Problems like this are usually solved using modular arithmetic.  In
modular arithmetic, we are only concerned with the remainder when a
number is divided by another.  The key to working with modular
arithmetic is that, because we are only interested in remainders, we
only need to use the remainders (instead of the actual numbers) in our
calculations.

For example, if I want to know the remainder when 3^175 is divided
by 7, I can do the following:

3/7 = 0 remainder 3
(3^2)/7 = (3*3)/7 = 9/7 = 1 remainder 2
(3^3)/7 = (3*2)/7 = 6/7 = 0 remainder 6

In that last calculation, I didn't multiply 3^2=9 by 3, because I am
only interested in remainders.  Instead, I multiplied 2 by 3,
because 2 is the remainder when 3^2=9 is divided by 7.

(3^4)/7 = (3*6)/7 = 18/7 = 2 remainder 4
(3^5)/7 = (3*4)/7 = 12/7 = 1 remainder 5
(3^6)/7 = (3*5)/7 = 15/7 = 2 remainder 1

Now, because our remainder is 1 at this point, when we multiply by 3
again, the pattern of remainders will start repeating.  So the
remainders we get when dividing successive powers of 3 by 7 is

3, 2, 6, 4, 5, 1

The pattern repeats every 6 powers.  The power in our problem is 175;
175/6 = 29 remainder 1.  That means the remainder when 3^175 is
divided by 7 is the same as the remainder when 3^1 is divided by 7;
and that remainder is 3.  So the remainder when 3^175 is divided by
7 is 3.

How do we use modular arithmetic on your problem?

First we note that the prime factorization of the divisor, 182, is

182 = 2*7*13

If the given number is divisible by 182, then it must be divisible
by 2, by 7, and by 13.

We can see that the number is divisible by 2 without using modular
arithmetic.  55^62 is odd; 2*(13^62) is even; and 41^62 is odd.  The
expression is then (odd - even + odd), which is even; so the
expression is divisible by 2.  (In fact, we are using modular
arithmetic--specifically, arithmetic "mod 2"--when we talk about even
and odd numbers.  But we don't need to use the formal modular
arithmetic methods, because it is easy to work with "odd" and "even"
numbers.)

To finish showing that the expression is divisible by 182, we can use
modular arithmetic to show that the expression is divisible by both 7
and 13.  The work is more complicated for 13 than for 7; so I'll show
you the details for 13 and let you try to fill in the details to show
the expression is divisible by 7.

So I need to show that

55^62 - 2*13^62 + 41^62

is divisible by 13.

The middle term has multiple factors of 13, so it is clearly
divisible by 13, so I only need to show that

55^62 + 41^62

is divisible by 13.  To do this, I look at the remainders when
successive powers of 55 and 41 are divided by 13.  Note that the
remainder when 55 itself is divided by 13 is 3, and the remainder
when 41 itself is divided by 13 is 2--so in fact I am going to look
for the patterns of remainders when 3 to successive powers and 2 to
successive powers are divided by 13.  Using the process demonstrated
above, I find...

3^1/13 --> remainder 3
3^2/13 = 3*3/13 --> remainder 9
3^3/13 = 3*9/13 --> remainder 1

AHA! I already have a remainder of 1; the pattern of remainders
repeats every 3 powers.  The power I want is 62; 62/3 leaves
remainder 2; so the remainder when 55^62 is divided by 13 is the same
as the remainder when 3^2 is divided by 13--which is 9.

And...

2^1/13 --> remainder 2
2^2/13 = 2*2/13 --> remainder 4
2^3/13 = 2*4/13 --> remainder 8
2^4/13 = 2*8/13 --> remainder 3
2^5/13 = 2*3/13 --> remainder 6
2^6/13 = 2*6/13 --> remainder 12

At this point I can use a "trick" of modular arithmetic.  The
remainder at this point when divided by 13 is 12; in modular
arithmetic I can think of this remainder as -1.  In other words, the
remainder is 1 less than the divisor.  For example, I can think of
19/5 as having remainder 4 (19 = 3*5 + 4) or as having remainder -1
(19 = 4*5 + (-1)).  Since 2^6 leaves remainder -1, I know that (2^6)^2
= 2^12 is going to leave remainder (-1)^2 = 1.  So the pattern of
remainders when successive powers of 2 are divided by 13 repeats every
12 powers.

Again, the power in my problem is 62; 62/12 = 5 remainder 2; so the
remainder when 41^62 is divided by 13 is the same as the remainder
when 2^2 is divided by 13--which is 4.

So now the remainders when the three parts of the given expression
are divided by 13 are 9, 0, and 4; the sum of those remainders is 13;
and 13 is divisible by 13.  So the entire expression is divisible by
13.

Now see if you can use the same type of process to show that the
expression is also divisible by 7....

I hope this helps.  Please write back if you have any further

- Doctor Greenie, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Number Theory
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