1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number of theory modulo

  1. Oct 17, 2012 #1
    1. The problem statement, all variables and given/known data

    Find the smallest natural number n such that: a^(3n)=a (mod 85) for each integer a.
    Justify your answer.

    2. Relevant equations

    3. The attempt at a solution

    because 85=17 . 5 and gcd (5,17)=1 we have to find the n such:

    a^(3n)=a (mod 5) and a^(3n)=a (mod 17).

    From Fermat theorem we know that a^(17)=a (mod 17) and a^(5)=a (mod 5)

    so we have: a^(5)=a^(3n) (mod 5) and a^(17)=a^(3n)(mod 17).

    I don't now how to continue and find the smallest natural n.
  2. jcsd
  3. Oct 17, 2012 #2
    You've already observed that it suffices to find a minimal n such that [itex]a^{3n} \equiv a \pmod{5}[/itex] and [itex]a^{3n} \equiv a \pmod{17}[/itex]. Here's a hint about how to do so:

    You already know that [itex]a^{5} \equiv a \pmod{5}[/itex]. Show that [itex]a^9 \equiv a \pmod{5}, a^{13} \equiv a \pmod{5}[/itex] and so on.

    Similarly, you know that [itex]a^{17} \equiv a \pmod{17}[/itex]. Show that [itex]a^{33} \equiv a \pmod{17}[/itex], and so on.

    Use the above to find the least exponent 3n such that [itex]a^{3n} \equiv a \pmod{5}[/itex] and [itex]a^{3n} \equiv a \pmod{17}[/itex].

    Please post again if you have any questions.
  4. Oct 18, 2012 #3
    i just do it. i find a^(33)=a(mod5) and a^(33)=a(mod17)
    now can i say that 3n=33 and n=11. is that right ???
  5. Oct 18, 2012 #4
    I got the same answer.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook