Prove an implication in modular arithmetic

Question

Prove for any integer $x$:

if $x^{13} = 1 \mod \ 17$ then $x = 1 \mod 17$

score 1 · Answer 1 · answered May 27 '20 at 19:51

$$x=(x^{13})^5(x^{16})^{-4}$$

Now apply Fermat little theorem

This will hold true for any odd integer $m$

All we need to find is Integers $a,b$ such that $$am+16b=1$$ which is always available using

https://artofproblemsolving.com/wiki/index.php/Bezout%27s_Lemma

score 1 · Answer 2 · answered May 27 '20 at 19:53

1

Hint: Take $x^{13}\equiv1\bmod17$ and raise both sides to the fifth power.

answered May 27 '20 at 19:53

J. W. Tanner

60,406

$5\times13=65=4\times16+1\equiv1\bmod16$, so using Fermat's Little Theorem $x^{65}\equiv x\bmod17$ – J. W. Tanner May 27 '20 at 19:55
1

We are currently studying that theorem I should have tried to exploit it. Thanks a lot for the help! – OUCHNA May 27 '20 at 20:07

score 0 · Answer 3 · answered May 27 '20 at 19:55

0

Since $17$ is a prime, all members of the multiplicative group mod $17$ have order dividing $17-1 = 16$. Since $13$ and $16$ are coprime, the order must be $1$, i.e. $x \equiv 1$.

answered May 27 '20 at 19:55

Robert Israel

448,999

Prove an implication in modular arithmetic

3 Answers3