Modular Arithmetic, and systematic approach.

[kioria]

Hi,

Can somebody drill me on the "congruences and modular arithmetic"? I know it is a big topic, but I think I am missing "something" in my knowledge... These things seem very unusual to me, and makes no sense sometimes.

Find smallest integer n, where:
3^n \equiv 1 (mod 7)

Is there a systematic way of doing a such thing?

[Muzza]

You could always apply Fermat's little theorem (it states that a^(p - 1) = 1 (mod p)), so n = 7 - 1 = 6 will work. But I don't know if it guarantees that this is the smallest such number in the general case (in this case it is, as good old-fashioned brute force reveals...).

[kioria]

You could always apply Fermat's little theorem (it states that a^(p - 1) = 1 (mod p)), so n = 7 - 1 = 6 will work. But I don't know if it guarantees that this is the smallest such number (in this case it is, as good old-fashioned brute force reveals...).

There are others such as:
5^n \equiv 1(mod 17) OR 5^n \equiv -1(mod 17)
In which case the n = 8.
So:
5^8 \equiv -1
Can somebody explain the above notation as well, thank you.

Very confusing to me right now.

[Muzza]

You can apply Fermat's little theorem on 5^n = 1 (mod 17) too. As for the second problem, I suppose "trying all possible values for n" classifies as systematic ;)

[matt grime]

To solve the ones equal to one, when you are working mod a prime remember that these things are a group. so the order must divide p-1, so it suffices to check the factors of p-1 in the exponent.

so for 3 mod 7, well, p-1=6 here, so you only need to check 1,2,3. Clearly none of these produces 1 mod 7 so the answer must be 6, and therefore 3 generates the units mod 7.

Now 5 mod 17, p-1=16, so you need to check the powers 1,2,4,8 (and again if none of those works then it must be that the order is 16).

Suppose you've found the answer, I don't know what it is by the way, as I'm too lazy to do it in my head. But suppose the order is r, it is even, so what is 5^{r/2}? it must be an element that squares to give 1, and at the same time can't be 1 (as r is minimal) so it must be -1 (there are only two square roots of any number mod a prime at most).

[kioria]

To solve the ones equal to one, when you are working mod a prime remember that these things are a group. so the order must divide p-1, so it suffices to check the factors of p-1 in the exponent.

so for 3 mod 7, well, p-1=6 here, so you only need to check 1,2,3. Clearly none of these produces 1 mod 7 so the answer must be 6, and therefore 3 generates the units mod 7.

Now 5 mod 17, p-1=16, so you need to check the powers 1,2,4,8 (and again if none of those works then it must be that the order is 16).

Thank you, so I will only need to check integers that are factors of p-1. Is that right? And, if it is right, in a test where calculators are not allowed, how would one check 5^{16}!! Total Insanity!

Suppose you've found the answer, I don't know what it is by the way, as I'm too lazy to do it in my head. But suppose the order is r, it is even, so what is 5^{r/2}? it must be an element that squares to give 1, and at the same time can't be 1 (as r is minimal) so it must be -1 (there are only two square roots of any number mod a prime at most).

I didn't get this part, r = 8, and the explainations following r I do not understand. Am I seriously missing something here?

[matt grime]

one wouldn't need to check 5^16

here's how to do it sans calculator (playing up to the pommie as much as I can)

5^2 = 25=8mod17

5^4=(5^2)^2 = 8^2=64 = 13 mod 17

5^8=((5^2)^2)^2 = 13^2 = 169 = 16=-1 mod 17

all done in my head, not even using paper.

as none of those is 1 it must be that the order is 16 (x^{p-1} is always 1 mod p a prime this never needs checking)


but in any case 5^16= (((5^2)^2)^2)^2 = (-1)^2 = 1 mod 17

in the process of this you see that 5^8=-1 and is the smallest power with this property. note that this is the order 5, 16, divided by two. that is not a coincidence. If you want to see why reread my post and think about it for a while.

[kioria]

thinking...

haha never knew what sans actually meant, looked it up on the dictionary, and it actually states: Rarely used as an English word. Wonder how else it is used.

[matt grime]

shakespeare, seven ages of man speech: sans teeth sans eyes.
wonder if the French are happy with us using their words, they don't like english ones in french after all. Oh, and today's cricket is rain affected.

which bit you thinking about? that when doing modulo arithmetic you dont; have to do all the arithmetic first then the modulo bit? useful observation.

suppose I wanted to work out (2^5)*(3^6)*(6^5)*(9^6) mod 17 well, I can note that 2*9=18=1 mod 17, and 3*6=1mod 18,, so that collecting and cancelling I end up with 3*9 = 27=10mod17

[kioria]

shakespeare, seven ages of man speech: sans teeth sans eyes.
I was never a strong contender for English during my high school years. So I guess sans is one of those archaic words, like thee, thy and thou. A new word in my vocab...

wonder if the French are happy with us using their words, they don't like english ones in french after all. Oh, and today's cricket is rain affected.
Only if I had time to watch my sports news, I have two tests tomorrow, and I can't afford to lose a mark. Aiming for HD average this semester... the first semester :D. I have to say, maths, I generally find it hard to understand its concepts but interesting enough to get me going forever just to understand one thing. By the way, you seem to be overloaded with maths knowledge, can I ask you what you do?

which bit you thinking about? that when doing modulo arithmetic you dont; have to do all the arithmetic first then the modulo bit? useful observation.

suppose I wanted to work out (2^5)*(3^6)*(6^5)*(9^6) mod 17 well, I can note that 2*9=18=1 mod 17, and 3*6=1mod 18,, so that collecting and cancelling I end up with 3*9 = 27=10mod17
Yes, modular arithmetic certainly is easier when carried out like you showed me. And interestingly, the part b) of the question I asked above was something like, Evaluate 5^{243} (mod 17) \equiv 6. And I did it! Thank you!

I still think I am mis-understanding some portions of Modular Arithmetic. But having this in my mind, I guess rest is upto my research (mind you this was the last part in the M.Arithmetic syllabus).

[honestrosewater]

I can't resist an opp to quote Shakespeare, so forgive me that it's not math related.
By my quick count, Shakespeare used the word "sans" 16 times, but I think its meaning is best exemplified by the line "My love to thee is sound, sans crack or flaw."
How could the French mind that? :)
Happy thoughts
Rachel
BTW I have just started reading Arthur Clarkes's translation of Gauss' Disquisitiones Arithmeticae, and, so far, it is the best explanation of modular arithmetic I've read. Maybe it would clear things up for you. Read the masters, right? :)

[Gokul43201]

So have I. I wish he would leave a blank line between results - would make it a lot easier on the eye.