Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm leaning congruency equations, so for example: $$ ax \equiv b \pmod m $$ I have that the number of solutions will be equal to $d$, where $$ d = \gcd(a, m). $$ And the solutions ae: $$ x, x+m/d, x+2m/d, x+3m/d, \ldots , x+(d-1)m/d $$ Now, having understood how I solve the equation, I am still not entirely sure as to why the number of solutions is given by $d$...

Anybody can calrify please?

Cheers! :)

share|improve this question
    
If $d$ does not divide $b$, there are no solutions. –  André Nicolas May 15 '13 at 22:07
    
Fair enough, but by are there precisely "d" solutions? –  max0005 May 15 '13 at 22:07
    
Will write an answer if no one else does soon. –  André Nicolas May 15 '13 at 22:09

2 Answers 2

up vote 2 down vote accepted

Let $d$ be a common divisor of $a$ and $m$. If the congruence $ax\equiv b\pmod{m}$ has a solution, then $ax-b$ is a multiple of $m$. Since $d$ divides both $m$ and $a$, it must divide $b$. In particular, if $d$ is the gcd of $a$ and $m$, the congruence has no solutions unless $d$ divides $b$. So from now on we suppose that $d$ divides $b$. Let $a=a_1d$, $m=m_1d$, and $b=b_1d$.

The congruence $a_1dx\equiv b_1d\pmod{m_1d}$ holds if and only if $m_1d$ divides $a_1d x -b_1d$. This is the case if and only if $m_1$ divides $a_1 x-b_1$, that is, if and only if $a_1x\equiv b_1\pmod{m_1}$.

So now consider the congruence $a_1x\equiv b_1\pmod{m_1}$. Since $d$ is the greatest common divisor of $a$ and $m$, it follows that the numbers $a_1$ and $m_1$ are relatively prime.

Because $a_1$ and $m_1$ are relatively prime, the congruence $a_1x\equiv b_1\pmod{m_1}$ has a unique solution modulo $m$. For a proof of uniqueness, we can use the fact that $a_1$ has an inverse $c$ modulo $m_1$. Then $ax\equiv b\pmod{m_1}$ if and only if $ca_1x\equiv cb_1\pmod{m_1}$, that is, if and only if $x\equiv cb_1\pmod{m_1}$. (One can also give a direct proof of uniqueness without using the inverse.)

So now we ask: given the unique solution $x$ modulo $m_1$, which numbers are congruent to $x$ modulo $m$? Certainly the numbers $x+\frac{im}{d}$ are, where $i$ ranges from $0$ to $d-1$. For these are the numbers $x+im_1$, and they are all congruent to $x$ modulo $m_1$.

Are there any others? Suppose that $y\equiv x\pmod{m_1}$. Then $m_1$ divides $y-x$. So the possible remainders when $y-x$ is divided by $m$ are $0, m_1,2m_1,\dots, (d-1)m_1$. It follows that $y-x=im_1$ for some $i$ where $0\le i\le d-1$. This just says that $y\equiv x+im_1 \pmod{m}$, that is, $y\equiv x+\frac{mi}{d}\pmod{m}$, for some $i$ ranging from $0$ to $d-1$.

Remark: The important part was the uniqueness modulo $m_1$. The rest is straightforward, and you know it well. To give a simple numerical example, suppose that we know that $x\equiv 3\pmod{16}$. What can we say about $x$ modulo $80$? We can say that $x$ is congruent to one of $3$, $19$, $35$, $51$, $67$.

share|improve this answer
    
Hi, just a question (may be I've been doing maths for too long), what does a = 1(1) mean in the first paragraph? –  max0005 May 15 '13 at 22:59
    
Anyway, think I've understood it, thanks :D –  max0005 May 15 '13 at 23:00
1  
@user1876047: It means there was a typo, it was supposed to be $a=a_1d$. Corrected. Thanks for finding it. –  André Nicolas May 15 '13 at 23:02
    
Also, hm, I understand d is gcd(a,m), but shouldn't it divide a and m for them to be relatively prime? If it multiplies it then they would both could be divided by d^2? –  max0005 May 15 '13 at 23:02
    
If $d$ is the gcd, and $a=a_1d$, $m=m_1d$, then $a_1$ and $m_1$ must be relatively prime, for if they had a non-trivial common divisor $e$, then $de$ would divide $a$ and $m$, so $d$ would not be their gcd. –  André Nicolas May 15 '13 at 23:06

If you scroll down on this pdf you will find a complete proof of this http://www.math.niu.edu/~richard/Math420/lin_cong.pdf

I couldn't be bothered to type it up. Sorry.

share|improve this answer
    
I'm sorry, but I still don't understand :S I see the range of solutions, but I don't see why it has to stop at gcd(a,m)-1... –  max0005 May 15 '13 at 22:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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