# Thread: Question to do with congreuncy

1. ## Question to do with congreuncy

Hi, i need help with the following question.
Let $\displaystyle a,b\in\mathbb{Z}$and $\displaystyle n\in\mathbb{N}$. Set $\displaystyle d=gcd(a,n)$.If $\displaystyle d\nmid b$ then prove that $\displaystyle ax\equiv b(modn)$has no integer solutions for $\displaystyle 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 $\displaystyle a,b\in\mathbb{Z}$and $\displaystyle n\in\mathbb{N}$. Set $\displaystyle d=gcd(a,n)$.If $\displaystyle d\nmid b$ then prove that $\displaystyle ax\equiv b(modn)$has no integer solutions for $\displaystyle x$.
Suppose towards a contradiction that $\displaystyle ax\equiv b\mod n$ has an integer solution.

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

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

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

EDIT: Ah, qmech beat me to it!

4. thank you.