Find x for which for every "a" the equation has solution $$a^{31x} \equiv a \mod 271$$
I need to find x variable, for which the equation has solution with any a. How can I do this?
Generaly, modular equations have solutions when $GCD(a^{31x}, 271) = 1$, or $GCD(a^{31x}, 271) = d > 1; d|a$
It also looks like I could use Little Fermat's Theorem...
But I can't come up with anything...
 A: If $271|a,271|(a^{31x}-a)$ for integer $x>0$
Else $(271,a)=1\implies 271|(a^{31x}-a)\iff 271(a^{31x-1}-1)$
Now as $271$ is prime, it has at least one primitive root,
the highest $ord_{271}(a)$ will be $271-1=270$ and the order of other numbers will be divisor of $270$
$\implies 270$ must divide $31x-1\iff 31x\equiv1\pmod {270}$
Now, $$\frac{270}{31}=8+\frac{22}{31}=8+\frac1{\frac{31}{22}}=8+\frac1{1+\frac9{22}}$$
$$=8+\frac1{\frac{31}{22}}=8+\frac1{1+\frac1{\frac{22}9}}=8+\frac1{1+\frac1{2+\frac49}}=8+\frac1{1+\frac1{2+\frac1{\frac94}}} =8+\frac1{1+\frac1{2+\frac1{2+\frac14}}}$$
So, the previous convergent of $\frac{270}{31}$ is $$8+\frac1{1+\frac1{2+\frac1{2}}}=\frac{61}7$$
Using Theorem $3$ of this,
$$ 31\cdot 61 -270\cdot7=1\implies 31\cdot61\equiv1\pmod{270} $$
$$\implies x\equiv61\pmod{270}$$
A: Since $271$ is prime, $\phi(271)=270$. Therefore,
$$
a^{31x}\equiv a\pmod{271}\tag{$\ast$}
$$
when
$$
31x\equiv1\pmod{270}
$$
We can solve $270y+31x=1$ using the Euclid-Wallis Algorithm:
$$
\begin{array}{r}
&&8&1&2&2&4\\\hline
1&0&1&-1&3&-7&31\\
0&1&-8&9&-26&61&-270\\
270&31&22&9&4&1&0
\end{array}
$$
Therefore, $61\times31\equiv1\pmod{270}$. Thus, if $x=61\pmod{270}$, then $(\ast)$ holds.
A: Since 271 is prime, we can indeed apply Fermat's little theorem.
Using this theorem we know that $a^{n}\equiv a \pmod{271}$ for any $n\equiv 1 \pmod{270}$.
Hence, we need to find an $x$ such that $31x\equiv 1\pmod{270}$.
To find an appropriate $x$ we may use the extended Euclidean algorithm:


*

*$ 0\cdot 31+1\cdot 270 = 270$

*$1\cdot 31+0\cdot 270 = 31$

*$ -8\cdot 31+1\cdot 270 = 22$

*$ 9\cdot 31-1\cdot 270 = 9$

*$-26\cdot 31+3\cdot 270 = 4$

*$61\cdot 31-7\cdot 270 = 1$


Thus $61\cdot 31\equiv 1 \pmod{270}$ and hence any $x\equiv 61\pmod {270}$ will do.
A: mod $\color{#c00}{27}\!:\, \dfrac{1}{31} \equiv\dfrac{28}4\equiv \color{#c00}7.\ $ mod $\color{#0a0}{10}\!:\, \dfrac{1}1 \equiv \dfrac{1}{31}\equiv \color{#c00}7\!+\!\color{#c00}{27}j\equiv-3\!-\!3j\,$ $\Rightarrow$ $\ 3j\equiv -4\equiv 6\,$ $\Rightarrow$ $\,j\equiv \color{#0b0}2.$
Thus $ $ mod $\,27\cdot 10\!:\ \dfrac{1}{31} \equiv 7\!+\!27j \equiv 7\!+\!27(\color{#0b0}2\!+\!\color{#0b0}{10}k) \equiv 61,\ $ by Chinese Remainder (CRT).
