1. Not finding help here? Sign up for a free 30min 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!

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:

    [tex]x^{46}\equiv1(mod47)[/tex]

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

    And when multiplying both sides by 46 we will get:
    [tex]46(x^{2})^{23}\equiv46*1^{23}(mod47)[/tex]

    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:
    [tex]x^{n}\equiv1(mod47)[/tex]

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

    [tex]x^{n}\equiv46(mod47)[/tex]

    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## ...
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Modular Arithmetic (someone check my work please)
  1. Check my work please? (Replies: 4)

  2. Please check my work (Replies: 2)

Loading...