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: Modular Arithmetic (someone check my work please)

  1. Mar 5, 2013 #1
    1. The problem statement, all variables and given/known data

    For every x in Z and for every natural number n if:

    [tex]x^{2}\equiv1(mod47)\Rightarrow x^{n}\equiv1(mod47)orx^{n}\equiv46(mod47)[/tex]

    3. The attempt at a solution

    Alright I said since 47 is prime and relatively prime with x then by fermat's little theorem we will get:


    and [tex](x^{2})^{23}\equiv1^{23}(mod47)[/tex] so that's case one.

    And when multiplying both sides by 46 we will get:

    which is [tex]x^{47}\equiv46(mod47)[/tex].

    So then i was able to conclude that if n=2k such that k is an integer we get:

    And if we have n=2k+1 (odd number) such that k is an integer we get:


    Is that correct?
  2. jcsd
  3. Mar 5, 2013 #2
    It seems like there are a lot of steps missing in this argument.

    Choosing n=1, it is clear that no more is needed than to show that ##x \equiv 1 \text{ mod } 47## or ##x \equiv 46 \text{ mod } 47##.

    Consider ##(x^2-1)##...
  4. Mar 5, 2013 #3

    Yea and x^-1=(x+1)(x-1)
  5. Mar 5, 2013 #4
    ... and we know that ##(x^2-1) \equiv 0 \text{ mod } 47## ...
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted