Show that $47$ divides $5^{23}+1$

Question

Show that $47$ divides $5^{23}+1$.

My attempt:

Since $47$ is prime and $47$ does not divide $5$, by Fermat's Little Theorem,

$5^{47-1} \equiv 1 \pmod {47}$

$5^{46} \equiv 1 \pmod {47}$

Now I noticed that $\mathbb{Z}_{47}$ was a field. So that means each element in $\mathbb{Z}_{47}$ has an multiplicative inverse in $\mathbb{Z}_{47}$. I went on to proceed to find the inverse of $5$ by the Extended Euclidean Algorithm which gave me $19$.

Now if I multiply both sides by $5^{-1}$ twenty-three times, I can reduce the power of $46$ to $23$,

Now, $(5^{-1} \cdot \ldots \cdot 5^{-1}) 5^{46} \equiv (5^{-1} \cdot \ldots \cdot 5^{-1}) \pmod {47}$

So, $5^{23} \equiv 19^{23} \pmod {47}$

But this didn't help me at all. So without giving the solution can someone give me a hint of a way to proving the above?

Answer 1

To be clearer with my suggestion, you correctly got to $5^{46} \equiv 1~(\text{mod} 47)$ from fermat's little theorem.

This tells me that $5^{23}\cdot 5^{23} \equiv 1~(\text{mod} 47)$ and so $5^{23}$ is its own inverse in $(\mathbb{Z}_{47}, \cdot)$. Since 47 is prime there is only one number that is it's own inverse so you can think of $5^{23} \equiv -1~(\text{mod} 47)$

Answer 2

I think you did all the hard work and got entangled with the easy one. As you said, we're working in a field, so:

== How many solutions on any field with characteristic $\;\neq2\;$ are there to $\;x^2-1=0\;$ ?

== Observe carefully what you wrote (everything's done modulo $\;47\;$):

$$1=5^{46}=\left(5^{23}\right)^2$$

Finish the proof.