# Understanding of the proof of “$d$ solutions for $kx \equiv l \pmod{m}$”

The question is from the proof of a theorem in Hardy's An Introduction to the Theory of Numbers.

THEOREM 57. If $(k, m) = d$, then the congruence $$(5.4.1)\qquad kx \equiv l \pmod{m}$$ is soluble if and only if $d|l$. It has then just $d$ solutions. In particular, if $(k, m) = 1$, the congruence has always just one solution.

Proof:
The congruence is equivalent to $$kx-my=l,$$

so that the result is partly contained in Theorem 25. It is naturally to be understood, when we say that the congruence has "just d" solutions, that congruent solutions are regarded as the same.

If $d = 1$, then Theorem 57 is a corollary of Theorem 56. If $d > 1$, the congruence (5.4.1) is clearly insoluble unless $d|l$. If $d|l$, then $$m = dm', \quad k = dk',\quad l = dl',$$ and the congruence is equivalent to $$(5.4.2)\qquad k'x \equiv l'\pmod{m'}.$$ Since $(k', m') = 1$, (5.4.2) has just one solution.

If this solution is $$x\equiv t\pmod{ m'},$$ then $$x=t+ym',$$ and the complete set of solutions of (5.4.1) is found by giving $y$ all values which lead to values of $t + ym'$ incongruent to modulus $m$. Since $$t+ym'\equiv t+zm'\pmod{m}\Leftrightarrow m|m'(y-z)\Leftrightarrow d|(y-z),$$ there are just $d$ solutions, represented by $$t, t + m', t + 2m',\cdots, t+(d-1)m'.$$ This proves the theorem.

Originally, the second last sentence is

Here are my questions:

• Is there a typo in the original text?

• Why are the $d$ solutions represented like that? What do the commas mean here? (Do they mean "or" or "and"?)

• What's the relationship between the last step in the proof and the question here?

-
Since Theorem 25 and Theorem 56 in the book are not directly related to my questions, I do not post them here. – Jack Jun 18 '11 at 2:07
The $t+tm'$ is a typo. Also, the final entry on that line looks like $t+(d-l)m'$ to me. If so, it's wrong, it should be $t+(d-1)m'$. Hardy and Wright is a lovely book to read, once you know some Number Theory. Something more modern might give a better start. There are even free texts online. – André Nicolas Jun 18 '11 at 2:31
Just for fun, I'm mentioning the worst typo I had ever seen... first time I read number theory, I came across this :  Wilson's Theorem. If $p$ is a prime, then $(p-1) \equiv -1 (\!\!\!\! \mod p)$. Proof. If $p=2$ or $p=3$, the congruence is easily verified. Thus we may assume that $p \ge 5$. Suppose that $1 \le a \le p-1$. Then $(a,p) = 1$, so that by Theorem 2.9 there is a unique integer $\overline a$ such that $a \overline a \equiv 1 (\!\!\!\! \mod p)$. (Few lines later, I saw the $(p-1)!$ appear and I googled.) Man did that proof scare me at first... – Patrick Da Silva Jul 30 '11 at 7:47

Edit: As mentioned in the comments, yes, it's not just the $t + tm'$, but the last one should read $t + (d-1)m'$. So there are two typos in that line from the book.

For congruences, you have both "and" and "or"! For example, consider \begin{align*} 3x \equiv 3 (\bmod 12) \end{align*} Now $\gcd(3,12) = 3$, so we expect 3 different solutions. One can easily find 1, 5, and 9 all work. Now the congruences classes of 1,5 and 9 modulo 12 are all different, hence in this setting they are 3 different solutions.

However, notice that 13 also works. In fact, any number of the form $12n + 1, 12n + 5$ or $12n + 9$ will work, as the 12 disappears modulo 12. So when you are considering multiple solutions to a congruence, \begin{align*} kx \equiv l (\bmod m) \end{align*} you want the "and" meaning for all the solutions that are distinct modulo $m$, and you want the "or" meaning when they are the same modulo class.

Hope this helps!

Added: I should add, for a congruence modulo $m$, we call the congruence class of $x$, the set $\{mn + x: n\in \mathbb{Z}\}$.

-
A nitpick: There is a second typo in the original text. The last solution in the list should be $(d-1)m'$ rather than $(d-l)m'$. – Doug Chatham Jun 18 '11 at 2:27
Oh yes, I didn't look that far.. At least that tells us for sure the 1 is not formatted oddly like a $t$ or and $l$ though! :) – Alex Jun 18 '11 at 2:29

First - there is a typo in the original text. Texts (mathematical or otherwise) are always full of typos, though some are worse than others. Use your common sense.

Second - there is more than one way to represent the solutions. For example, any $d$ consecutive multiples of $m'$ would do. More concretely, you could replace all $+$s with $-$s. The specific set was chosen for no particular reason. No, that's actually a lie. It was chosen since it is the first that comes to mind.

Third - the commas here serve to separate items in a list. For example "in this shop one could buy apples, oranges, pears and bananas". Or "please get me an apple, an orange or a pear". Or "please select two of the following pieces for your test: Hamlet, Macbeth, King Lear, Othello".

-