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 
questions about any of this.

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/