- #1
mtayab1994
- 584
- 0
Homework Statement
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]
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?