1

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?

Rócherz
  • 3,976
Bobby
  • 775
  • I'm assuming you mean without a calculator, right? – Pakquebchsoflwty Oct 26 '14 at 03:36
  • @Pakque Yes that's correct. – Bobby Oct 26 '14 at 03:37
  • $-1\cdot -1 = 1$. It is okay to refer to negative numbers when it makes your life simpler. – JMoravitz Oct 26 '14 at 03:38
  • 1
    You know that $(5^{23}-1)(5^{23}+1) = 5^{46}-1 \equiv 0\pmod{47}$. Since $47$ is prime, that means at least one of $5^{23}-1$ and $5^{23}+1$ must be divisible $47$. – JimmyK4542 Oct 26 '14 at 03:38
  • Also, the numbers are small enough that repeated squaring is doable by hand. Successively compute, $5^2 \pmod{47}$, $5^4 \pmod{47}$, $5^8 \pmod{47}$, $5^{16} \pmod{47}$, $5^{24} \pmod{47}$, and finally $5^{23} \pmod{47}$. – JimmyK4542 Oct 26 '14 at 03:51
  • @JimmyK4542 Mmm, all I need now is to show that $5^{23} - 1$ is not divisible by $47$ Since if $p$ is prime and $p$ divides $ab$ then $p$ divides $a$ or $b$ – Bobby Oct 26 '14 at 03:53

2 Answers2

0

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

JMoravitz
  • 79,518
0

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.

Timbuc
  • 34,191