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!

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

Have something to add?
Draft saved Draft deleted

Similar Threads - Modular Arithmetic someone Date
Modular arithmetic on vector spaces Feb 23, 2016
Modular Arithmetic Congruence Oct 15, 2014
Binomial theorem and modular arithmetic Aug 28, 2014
Proof: Modular Arithmetic Sep 18, 2013
Primes, pigeon holes, modular arithmetic Nov 27, 2012