0
$\begingroup$

I am self studying Apostol Dirichlet series and Modular functions in number theory and I am struck on Ch -2 Problem 17. It is a problem of elementary number theory but I am not able to think about it.

Question: if a, b, n are integers with n greater than or equal to 1 and ( a, b, n) =1 , then prove that the congruence ax- by=1 ( mod n) has exactly n solutions, distinct mod n.


I tried using solutions of diophantine equation ax+by= c but can't do it. Please help

$\endgroup$
1
$\begingroup$

Let $\gcd(a,n)=d$. Then $\gcd(b,d)=1$, so $by+1\equiv0\bmod d$ has a unique solution mod $d$, which lifts to $n/d$ solutions mod $n$. For each of those $n/d$ values of $y$, $(a/d)x\equiv(by+1)/d\bmod{n/d}$ has a unique solution mod $n/d$, which lifts to $d$ solutions mod $n$. So we have $n/d$ values of $y$, and, for each of them, $d$ values of $x$, hence, all told, $(n/d)d=n$ solutions.

$\endgroup$

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.