# Method to find solution for $a^x \equiv \mod n$ [closed]

The congruence $$5^x \equiv 1 \mod 36$$ has a solution because $$5$$ and $$36$$ are relatively prime, i.e. $$5$$ and $$2^23^2$$ have no common factors.

Is there a method to find $$x$$?

All I can see is that $$5^3 \equiv 5 \mod 6$$.

## closed as off-topic by Carl Mummert, Xander Henderson, Lee David Chung Lin, Eevee Trainer, CesareoMar 6 at 8:53

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Carl Mummert, Xander Henderson, Lee David Chung Lin, Eevee Trainer, Cesareo
If this question can be reworded to fit the rules in the help center, please edit the question.

• What do you want to know? i.e. $a^x \equiv$ what? – joseph Feb 27 at 15:28
• @josephF Note that $5^{37} \equiv 5 \mod 36$, so your answer needs editing. – Jossie Calderon Feb 27 at 15:31
• what answer are you talking about? – joseph Feb 27 at 18:11

Hint

$$(6-1)^n\equiv(-1)^n+(-1)^{n-1}6n\pmod{36}$$

Check for odd$$(2m+1)$$ & even$$(2m)$$ values of $$n$$

• – lab bhattacharjee Feb 27 at 15:28
• Unrelated, but does Dummit and Foote go over it in their book? – Jossie Calderon Feb 27 at 15:34

You could always use the Chinese Remainder Theorem for congruences like this.

For $$5^x\equiv 1 \ \bmod 36$$

you should solve

$$\begin{cases} 5^x\equiv 1 \ \bmod 4\\ 5^x\equiv 1 \ \bmod 9 \end{cases}$$

This way you have to deal with smaller moduli.

• The same question still applies: What's the method? – Jossie Calderon Feb 27 at 15:36

In other words you want to find the multiplicative order of $$5$$ mod $$36$$. By Euler's theorem this divides $$\varphi(36) = 12$$. Next step: try $$12/2 = 6$$ and $$12/3 = 4$$.

Hint $$\ a\equiv 1\pmod{np}\ \Rightarrow\, a^{\large p}\equiv 1\pmod{np^2}\$$ by $$\,a^{\large p}\!-1 = (\overbrace{a-1}^{\large np\,k})(\!\overbrace{a^{p-1}+\cdots+a^2+a+1}^{\large\ \ \equiv\ 1+\cdots+1\ \equiv\ p\,\cdot 1\ \equiv\ 0\pmod{\!p}\!\!\!\!\!}\!\!)$$

$${\rm thus}\,\ 5^{\large 2}\!\equiv 1\pmod{\!4\cdot 3}\Rightarrow 5^{\large 6}\!\equiv 1\pmod{\!4\cdot 3^2}$$

Remark  To learn more about this general idea see LTE = Lifting The Exponent

• But 36 is not a prime, so i'm confused. Does the rule apply to $2^2$ and $3^2$? – Jossie Calderon Feb 28 at 4:54
• @Jossie We used $\,a=5^2,\ n =4,\ p = 3.\$ Note $\,p\,$ can be any natural - see the proof. – Bill Dubuque Feb 28 at 14:36