2
$\begingroup$

How does on solve for $x$ in

$x^k \equiv b \pmod n$

where $n$ is not prime and $\gcd(k,\phi(n)) > 1$

Can this be done using Euler's theorem and totient function?

  • 0
    Do you mean $\gcd(n,x) > 1$?2011-10-13
  • 0
    No. There is a method to solve a congruence where you use the equation $ku - \phi(n)v = 1$ and find $u$ and $v$. Then use those numbers to solve for $x$. This method does not work, however, when $gcd(x,n) > 1$.2011-10-13
  • 0
    ehh yeah, nevermind, I read that wrong.2011-10-13
  • 1
    $x^k \equiv x^{k-\phi(n)}$, where $\phi(n)$ is Euler's totient function. At least as long as $x$ and $n$ are coprime. So you can assume that $k$ is smaller than $\phi(n)$. That is as much as the theorem and totient function can help you.2011-10-13
  • 0
    Which $\gcd$ is $>1$? In the post it is $\gcd(n,k)$, in a comment it is the puzzling $\gcd(x,n)$. But the equation $ku-\varphi(n)v=1$ implies $\gcd(k, \varphi(n))=1$, which raises the possibility that your assumption is meant to be the more natural $\gcd(k,\varphi(n))>1$.2011-10-13
  • 0
    Andre, you're correct. That was a typo in the comment, and it should be $gcd(k,\phi(n)) > 1$.I updated the question to reflect this. Thank you for your feedback.2011-10-13
  • 0
    I took the liberty of making that same change to the title :-)2011-10-13

1 Answers 1