d Solutions

[Xittenn]

The following is taken from "An Introduction to the Theory of Numbers" - G. H. Hardy & E. M. Wright; 6th Edition, page 62

 

Theorem 57. If [math] (k,m) = d, [/math] then the congruence (5.4.1) [math] kx \equiv l ( mod \;m ) [/math] is soluble if and only if [math] d|l [/math]. It has then just [math] d [/math] solutions. In particular, if [math] (k,m)=1 [/math], the congruence has always just one solution.

 

I'm having a hard time with the proof that "It has then just [math] d [/math] solutions."

 

The following is clear up until the last point:

 

If [math] d|l [/math], then [math] m = dm', \; k=dk', \; l=dl' [/math], and the congruence is equivalent to (5.4.2) [math] k'x \equiv l'(mod \; m') [/math].

 

Since [math] (k',m')=1 [/math], (5.4.2) has just one solution. If this solution is [math] x \equiv t(mod \; m'), [/math] then [math] x = t + ym', [/math] and the complete set of solutions of (5.4.1) is found by giving [math] y [/math] all values which lead to values of [math] t+ym' [/math] incongruent to modulus [math] m [/math].

 

Since [math] t+ym' \equiv t + zm'(mod \; m) \equiv m|m'(y-z) \equiv d|(y-z), [/math] there are just [math] d [/math] solutions, represented by [math] t, t+tm' t+2m',...., t+(d-l)m'. [/math]

 

I understand the cascade of congruences on this last point but I fail to understand how it proves that if [math] d|l [/math] where [math] d > 1 [/math] that there are [math] d [/math] solutions . . . .

 

appreciate any thoughts,

 

Xittenn

Edited October 14, 2011 by Wuz Here

[Xittenn]

Proper terminology for this theorem seems to be the Solution of Linear Congruence. I'll look harder next time.

[DrRocket]

The following is taken from "An Introduction to the Theory of Numbers" - G. H. Hardy & E. M. Wright; 6th Edition, page 62

 

Theorem 57. If [math] (k,m) = d, [/math] then the congruence (5.4.1) [math] kx \equiv l ( mod \;m ) [/math] is soluble if and only if [math] d|l [/math]. It has then just [math] d [/math] solutions. In particular, if [math] (k,m)=1 [/math], the congruence has always just one solution.

 

I'm having a hard time with the proof that "It has then just [math] d [/math] solutions."

 

The following is clear up until the last point:

 

If [math] d|l [/math], then [math] m = dm', \; k=dk', \; l=dl' [/math], and the congruence is equivalent to (5.4.2) [math] k'x \equiv l'(mod \; m') [/math].

 

Since [math] (k',m')=1 [/math], (5.4.2) has just one solution. If this solution is [math] x \equiv t(mod \; m'), [/math] then [math] x = t + ym', [/math] and the complete set of solutions of (5.4.1) is found by giving [math] y [/math] all values which lead to values of [math] t+ym' [/math] incongruent to modulus [math] m [/math].

 

Since [math] t+ym' \equiv t + zm'(mod \; m) \equiv m|m'(y-z) \equiv d|(y-z), [/math] there are just [math] d [/math] solutions, represented by [math] t, t+tm' t+2m',...., t+(d-l)m'. [/math]

 

I understand the cascade of congruences on this last point but I fail to understand how it proves that if [math] d|l [/math] where [math] d > 1 [/math] that there are [math] d [/math] solutions . . . .

 

appreciate any thoughts,

 

Xittenn

 

Note that solutions are congruence classes, as is stated earlier in the text (though you did not quote that part. Since, as you quoted, Hardy and Wright explicitly list the d solutions, I don't understand what it is that you do not understand. There are d of them -- (fixing the typos in the 6th edition) [math] t, t+m', t+2m',...., t+(d-1)m'. [/math]

Edited October 16, 2011 by DrRocket

[Xittenn]

well the [math] t+tm' [/math] and [math] t+(d-l)m' [/math] typo's were a bit much for me . . .

Edited October 16, 2011 by Wuz Here

[DrRocket]

well the [math] t+tm' [/math] and [math] t+(d-l)m' [/math] typo's were a bit much for me . . .

 

Be careful. Apparently typos were introduced when the 6th editions was typeset. This one, at least, does not occur in the 4th edition.