Congruence Class of 10^n Modulo 11

Date: 04/14/2003 at 09:16:21
From: Matt
Subject: Congruence class of 10^n modulo 11

What is the congruence class of 10^n modulo 11? Use this to determine 
the remainder when 654321 is divided by 11.

What does it mean to say that 10^n mod 11 belongs to a congruence 
class?

I know that 654321 =  8 (mod 11) but I don't know how that will help 
me in this problem.

Date: 04/27/2003 at 15:03:00
From: Doctor Nitrogen
Subject: Re: Congruence class of 10^n modulo 11

Hi, Matt:

To find the congruence classes 10^n modulo 11, you can start by
looking at those integers b and r which satisfy, by the Division 
Algorithm:

   10^n = b*11 + r, where

   0 <= r < 11.

For any positive integer m, there are m congruence classes 
modulo m. To illustrate: for m = 11 they are those integers 
in each of the eleven infinite sets:       

  congruent to 0 modulo 11: {..., -11, 0, 11, 22, 33, 44, 55, ...}

  congruent to 1 modulo 11: {..., 1, 12, 23, 34, 45, 56, ...}

  congruent to 2 modulo 11: {..., 2, 13, 24, 35, 46, 57, ...}

  congruent to 3 modulo 11: {..., 3, 14, 25, 36, 47, 58, ...}
    .
    .
  congruent to 10 modulo 11: {..., 10, 21, 32, 43, 54, 65, ...}

These are the 11 congruence classes modulo 11.

With a little experimentation, you can find, for each fixed 

   n = 1, 2, 3, ...

which congruence class each integer

   10^n 

will belong to. For example, 

  10^1 can be found in the congruence class 10 modulo 11.

  10^2 can be found in the congruence class 1 modulo 11.

  10^3 can be found in the congruence class 10 modulo 11.

  10^4 can be found in the congruence class 100 modulo 11. 

  10^5 can be found in the congruence class 1000 modulo 11. 

  10^6 can be found in the congruence class 10000 modulo 11. 

The ten congruence classes modulo 11 form ten equivalence classes 
modulo 11. 

Now all these above look like 

   10^n is congruent to 10^s modulo 11, 

where s is some integer less than n, and

   10^n - 10^s

is divisible by 11.

Is there a continuing pattern here? Try more values for n and then 
see if you can conjecture something.

I hope this helped answer the questions you had concerning your 
mathematics problem. 

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