• We’re currently investigating an issue related to the forum theme and styling that is impacting page layout and visual formatting. The problem has been identified, and we are actively working on a resolution. There is no impact to user data or functionality, this is strictly a front-end display issue. We’ll post an update once the fix has been deployed. Thanks for your patience while we get this sorted.

Math problem (discrete/modular arithmetic/number theory). need some help.

S

Scrapster

Diamond Member
Problem:

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

For the first part, from my analysis there are 11 possible classes ranging from 0 - 10. The n is throwing me off, I'm not sure how to incorporate that yet.

For the second part, well, I'll figure that out when I get #1.
 
I dont mean to sound like an ass but you really should try to figure out this stuff, if people keep telling you you'll never learn it.
 
I dont mean to sound like an ass but you really should try to figure out this stuff, if people keep telling you you'll never learn it.

I've already put in 3 hours into this problem. Trust me, I don't come here unless I'm *REALLY* stuck.
 
congruence class of 10^n modulo 11.

refer to my post of the non comp sci description of modulus in your other thread =)

the congruence class of 10^n modulo 11 is the set of numbers that produce the same remainder.

yes there are 11 distinct congruence classes.

=> refers to the class

when n = 1: 10^n = 10 => {10} => {-1}
when n = 2: 10^n = 100 => {1}
when n = 3: 10^n = 1000 = 990 + 10 = 0 + 10 = 10
when n = 4: 10^n = 10000 = 9999 + 1 = 1

etc =)

notice when i made {10} = {-1} that is what i meant in the other thread about representing numbers cheaply =)
 
notice how 10 = -1 (mod 11)
and how 100 = 1 (mod 11)

notice how -1 + 1 = 0, and how 10 + 100 = 110 = 0 (mod 11)

=)
 
You're supposed to use the 1st problem as a hint to quickly find the answer to the 2nd problem.

For the 1st problem, try playing around with several values of n to see a pattern.

For n=1, what is the congruence class of 10^1 mod 11? This is the same as 10 mod 11.

The answer is 10.

For n=2, what is the congruence class of 10^2 mod 11? This is the same as 100 mod 11.

The answer is 1.

For n=3, what is the congruence class of 10^3 mod 11? This is the same as 1000 mod 11.

The answer is 1.

Can you see a pattern? So far we have seen two difference congruence classes. {1, 10}. What would the congruence class be for n=4?

Can you get any other congruence class besides 1 and 10?
 
now what is 654321?

it is 6 * 10^6 + 5*10^5 etc.


Ok M, I followed your clue all the way to 10^0. And I see how that will lead you to the original number. But I haven't made the connection between that pattern and 8 (which is the remainder). What's another clue?
 
WAIT A SECOND! Let me float this one.

We can partition 654321 a bit (i think this is where M was going). Then can we use the class # to substitute for segments of 654321 until we get smaller numbers to deal with? Ok. Maybe I'm full of crap.
 
i made a mistake above, it's 6*10^5 + 5*10^4 etc...

two ways to think about it.

6*10^5 = (6 * 10^5) = (6 * 100000) = [6*(99990 + 10)] => 6*10 => 6*-1 = -6 => 5

6*10^5 = (6 * 10^5) = (6 * 100000) = [6*(99990 + 10)] => 6*10 => 60 = 55 + 5 => 5

soooooooooooooooo...

2 ways to think

654321 = 6*10^5 + 5*10^4 + 4*10^3 + 3*10^2 + 2*10^1 + 1*10^0 = 6*10 + 5*1 + 4*10 + 3*1 + 2*10 + 1*1 = 60+5+40+3+20+1 = 129 = 121 + 8 = 8

654321 = 6*10^5 + 5*10^4 + 4*10^3 + 3*10^2 + 2*10^1 + 1*10^0 = 6*-1 + 5*1 + 4*-1 + 3*1 + 2*-1 + 1*1 = -6+5-4+3-2+1 = -3 = 8
 
btw, you don't have to do any iterations of 10^n...

10^2 = 10 (10^1) = 10 {-1} = {-10} = 1

10^3 = 10{-10} = 10{1} = {10} = {-1}

etc...

so, all you can get are 1, -1, etc.
 
the strength in modulus is this...

in mod 11

there are 2 ways to represent the equivalence classes

the obvious way is this {1,2,3,4,5,6,7,8,9,10,11 = 0}

the smart way is this {1,2,3,4,5,-5,-4,-3,-2,-1,0}

makes for much simpler math =)
 
You must log in or register to reply here.

TRENDING THREADS

Back
Top