1
$\begingroup$

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

$\endgroup$

closed as off-topic by Carl Mummert, Xander Henderson, Lee David Chung Lin, Eevee Trainer, Cesareo Mar 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.

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

Hint

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

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

$\endgroup$
0
$\begingroup$

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.

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

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

$\endgroup$
0
$\begingroup$

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

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

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