Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

4 Answers 4

up vote 1 down vote accepted

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.

share|improve this answer
    
It should be mentioned that there exists at least one element of order $=270$ (i.e., primitive root) and the order of all other numbers will divide $270$. –  lab bhattacharjee May 21 '13 at 16:07

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
    
The point is to show how to use CRT to compute modular inverses. Since the first step using little Fermat has already been mentioned a few times in other answers, I omit it above. –  Key Ideas May 21 '13 at 16:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.