Congruence Class of 10^n Modulo 11Date: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/