# Math Help - Question to do with congreuncy

1. ## Question to do with congreuncy

Hi, i need help with the following question.
Let $a,b\in\mathbb{Z}$and $n\in\mathbb{N}$. Set $d=gcd(a,n)$.If $d\nmid b$ then prove that $ax\equiv b(modn)$has no integer solutions for $x$.

2. You're given ax-mn=b for some integral m. d divides the LHS, but not the RHS, which is impossible for integral a,x,m,n & b.

3. Originally Posted by cooltowns
Hi, i need help with the following question.
Let $a,b\in\mathbb{Z}$and $n\in\mathbb{N}$. Set $d=gcd(a,n)$.If $d\nmid b$ then prove that $ax\equiv b(modn)$has no integer solutions for $x$.
Suppose towards a contradiction that $ax\equiv b\mod n$ has an integer solution.

Then $n\big|(ax-b)$ and $d\big|(ax-b)$, such that

$ax\equiv b\mod d$ and $0\equiv b\mod d$,

meaning $d\big|b$, which is a contradiction.

EDIT: Ah, qmech beat me to it!

4. thank you.