If $x^5 ≡ 2 $(mod $17$) then $x ≡ 15 $(mod $17$)

Question

How am I suppose to reduce the $x^5$ Should I write the entire table ?

score 3 · Answer 1 · answered Mar 07 '16 at 02:53

3

You probably know that $x^{p-1}\equiv 1 \pmod p$ for non-zero $x$. So in our case the exponent we have, $5$, is relatively prime to $p-1=17-1=16$. So there exist integers $a,b$ such that $5a+16b=1$. (E.g. $a=-3,b=1$) does So $x\equiv x^{5a+16b}\equiv x^{5a}(x^{16})^b\equiv x^{5a}\equiv (x^5)^a\equiv 2^{-3}\equiv 2^{16-3}\equiv 2^{13} \pmod {17}$.

Now $2^{13}$ reduces to $15$ modulo 17.

answered Mar 07 '16 at 02:53

Arkady

9,315

So we know 5 and 16 are coprime. How do you get 5a + 16b = 1 ? – Ming Wu Mar 07 '16 at 03:03
In general if $\gcd(x,y)=k$, you can always find integers $a,b$ such that $ax+by=k$. – Arkady Mar 07 '16 at 03:04
omg ur absolutely right? I forgot about that theorem. Thanks – Ming Wu Mar 07 '16 at 03:07
How is $2^{-3}$ = $2^{16-3}$ – Ming Wu Mar 07 '16 at 03:35
Because $2^{16}\equiv 1 \pmod 17$ You can multiply by $(2^{16})^k$ for free anywhere in your calculations. – Arkady Mar 07 '16 at 03:39

score 0 · Accepted Answer · answered Mar 07 '16 at 03:35

0

FLT $x^{16}\equiv 1 \mod 17$

So $(x^5)^3x \equiv 8x \equiv 1 \mod 17$

So $16x \equiv -x \equiv 2 \mod 17$

So $x \equiv -2 \equiv 15 \mod 17$

answered Mar 07 '16 at 03:35

fleablood

124,253

If $x^5 ≡ 2 $(mod $17$) then $x ≡ 15 $(mod $17$)

2 Answers2