Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular Arithmetic, and systematic approach.

  1. Apr 18, 2004 #1

    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:
    [tex]3^n \equiv 1 (mod 7)[/tex]

    Is there a systematic way of doing a such thing?
  2. jcsd
  3. Apr 18, 2004 #2
    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...).
    Last edited: Apr 18, 2004
  4. Apr 18, 2004 #3
    There are others such as:
    [tex]5^n \equiv 1(mod 17)[/tex] OR [tex]5^n \equiv -1(mod 17)[/tex]
    In which case the n = 8.
    [tex]5^8 \equiv -1[/tex]
    Can somebody explain the above notation as well, thank you.

    Very confusing to me right now.
    Last edited: Apr 18, 2004
  5. Apr 18, 2004 #4
    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 ;)
  6. Apr 18, 2004 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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).
  7. Apr 18, 2004 #6
    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 [tex]5^{16}[/tex]!! Total Insanity!

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

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
  9. Apr 18, 2004 #8

    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.
  10. Apr 18, 2004 #9

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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
    Last edited: Apr 18, 2004
  11. Apr 18, 2004 #10
    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...

    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?

    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 [tex]5^{243} (mod 17) \equiv 6[/tex]. 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).
    Last edited: Apr 18, 2004
  12. Apr 23, 2004 #11


    User Avatar
    Gold Member

    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
    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? :)
    Last edited: Apr 23, 2004
  13. May 7, 2004 #12


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    So have I. I wish he would leave a blank line between results - would make it a lot easier on the eye.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook