3
$\begingroup$

How can I show that $x \equiv b^{u} \pmod m$ is always a solution to $x^{k} \equiv \pmod m$, even if $\gcd(b,m) \gt 1$?

Our method for solving something like $x^k \equiv b\pmod m$ is first to find the integers $u$ and $v$ satisfying $ku - \phi (m)v = 1$, and then the solution is $x\equiv b^u \pmod m$. However, we only showed that this works provided that $\gcd(b,m) = 1$, since we used Euler's formula $b^{\phi(m)} \equiv 1\pmod m$.

If $m$ is a product of distinct primes, how can I show that $x \equiv b^{u} \pmod m$ is always a solution to $x^{k} \equiv \pmod m$, even if $\gcd(b,m) \gt 1$ ?

Also, why doesn't this method work for the congruence $x^5 \equiv 6 \pmod 9$ ?

$\endgroup$
  • $\begingroup$ Anyone understand? $\endgroup$ – user274933 Oct 2 '15 at 16:06
  • $\begingroup$ Clearly you can't prove something for which you already have a counterexample. $\endgroup$ – lhf Oct 2 '15 at 16:13
  • $\begingroup$ No the method I am asking about works. There is a reason that the example is different $\endgroup$ – user274933 Oct 2 '15 at 16:16
  • $\begingroup$ The method does not work for $x^5 \equiv 6 \bmod 9$ because $5\cdot 5 \equiv \bmod 6 = \phi(9)$ but $6 ^5 \equiv 0 \not\equiv 6 \bmod 9$. The reason of course is that Euler's theorem does not apply in this case. $\endgroup$ – lhf Oct 2 '15 at 16:19
  • $\begingroup$ Thank you. Now I just need to show that $x≡b^{u}(mod m)$ is a solution to $x^{k}≡(mod m)$ .. $\endgroup$ – user274933 Oct 2 '15 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.