Homework Help: Modular Arithmetic (someone check my work please)

1. Mar 5, 2013

mtayab1994

1. The problem statement, all variables and given/known data

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

$$x^{2}\equiv1(mod47)\Rightarrow x^{n}\equiv1(mod47)orx^{n}\equiv46(mod47)$$

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:

$$x^{46}\equiv1(mod47)$$

and $$(x^{2})^{23}\equiv1^{23}(mod47)$$ so that's case one.

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

which is $$x^{47}\equiv46(mod47)$$.

So then i was able to conclude that if n=2k such that k is an integer we get:
$$x^{n}\equiv1(mod47)$$

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

$$x^{n}\equiv46(mod47)$$

Is that correct?

2. Mar 5, 2013

Joffan

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)$...

3. Mar 5, 2013

mtayab1994

Yea and x^-1=(x+1)(x-1)

4. Mar 5, 2013

Joffan

... and we know that $(x^2-1) \equiv 0 \text{ mod } 47$ ...