2

I want to show, that $5^{96}\equiv -1 \pmod{193}$, without using the formula for quadratic residue. So far I have :

$5^{96}\equiv 5^{4\cdot24} \equiv 625^{24}\equiv 46^{24}\equiv 186^{12}\equiv -7^{12}\equiv 7^{12}\equiv 7^{3\cdot4}\equiv 150^4\equiv -43^4\equiv 43^4\equiv 112^2\equiv -81^2\equiv 3^8\\\ $

I think Euler's totient doesn't help, as $\varphi(193)=192>96=\frac{192}{2}$ or can I write this ? $5^{96}\equiv 5^{192-96} \equiv 5^{-96}\equiv(5^{-1})^{96}\equiv 116^{96}\equiv -77^{96} \pmod{193} $

What am I doing wrong ? What am I missing ? Thanks in advance.

gagamaga
  • 99

2 Answers2

1

Let $x=5^{96}$. Then in the field $\Bbb F_{193}$ we have $$ 1=5^{\phi(193)}=(5^{96})^2=x^2, $$ so that $(x-1)(x+1)=0$ in $\Bbb F_{193}$. Since a field has no zero divisors, we must have either $x=1$ or $x=-1$.

But $5^4=625=46$, so that $5^8=46^2=186$ and $5^{16}=49$, $5^{32}=85$, so that $$ 5^{96}=(5^{32})^3=85^3=-1. $$

Your calculation is correct, too, since $$ 3^8=6561=-1. $$

Dietrich Burde
  • 130,978
1

Another idea: since $96$ is a multiple of $3$ and you know $(5^{96})^2\equiv 1$, you have $(5^{32})^3\pm 1\equiv 0$. Factor this using the familiar factorization for the sum or difference of cubes:

$5^{96}\pm1=(5^{32}\pm1)×(5^{64}\mp5^{32}+1)$

Now square $5$ six times to get

$5^2\equiv 25, 5^4\equiv 46, 5^8\equiv 186\equiv -7, 5^{16}\equiv 49, 5^{32}\equiv 85, 5^{64}\equiv 84$.

Then $5^{64}-5^{32}+1\equiv 0$ and this is a factor of $5^{96}+1$, forcing $5^{96}\equiv -1$.

Oscar Lanzi
  • 39,403