1
$\begingroup$

I am working on the following question and am unsure how to proceed.

"Let a,n be positive integers and let d = gcd(a,n). Show that the equation ax ≡ 1(n) has a solution iff d = 1."

I know that $a^{\phi(n)} \equiv 1$ (mod n) when (a,n) = 1, by the Euler-Fermat theorem however I am not sure if this is as useful as I think it is. Any help is appreciated.

$\endgroup$
1
$\begingroup$

You are essentially finished, let $x=a^{\varphi(n)-1}$.

$\endgroup$
  • $\begingroup$ Thank you. I cannot believe that I did not see that sooner... $\endgroup$ – letsmakemuffinstogether Sep 17 '15 at 18:11
  • $\begingroup$ You are welcome. There are other ways to prove that if $\gcd(a,b)=1$ then there exist integers $x$ and $y$ such that $ax+by=1$. One way is to run the Euclidean Algorithm and then calculate backwards to find $x$ and $y$. There are several other proofs. $\endgroup$ – André Nicolas Sep 17 '15 at 18:18

Your Answer

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

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