# Solving a linear congruence

• Nov 29th 2009, 05:30 PM
oldguynewstudent
Solving a linear congruence
Hi again,

From practice questions for upcoming test:

Solve the linear congruence: 4x $\equiv$ 5 (mod 11)

First find the inverse, 11 = (2)(4) + 3; 4 = (1)(3) + 1

so 3 = 11 + (-2)(4) and 1 = 4 - 3 = 4 - [ (1)(11) + (-2)(4)] = (-1)(11) + (3)(4)

So 4(3) $\equiv$ 1 (mod 11) and 4(15) $\equiv$ 5 (mod 11)

Therefore the solution is x = 15.

Is the above correct? Or since 15 -11 = 4 and 0 < 4 < 11, would 4 be a more correct answer?
• Nov 29th 2009, 07:54 PM
tonio
Quote:

Originally Posted by oldguynewstudent
Hi again,

From practice questions for upcoming test:

Solve the linear congruence: 4x $\equiv$ 5 (mod 11)

First find the inverse, 11 = (2)(4) + 3; 4 = (1)(3) + 1

so 3 = 11 + (-2)(4) and 1 = 4 - 3 = 4 - [ (1)(11) + (-2)(4)] = (-1)(11) + (3)(4)

So 4(3) $\equiv$ 1 (mod 11) and 4(15) $\equiv$ 5 (mod 11)

Therefore the solution is x = 15.

Is the above correct? Or since 15 -11 = 4 and 0 < 4 < 11, would 4 be a more correct answer?

Not more correct, but undoubtedly nicer and more widely accepted since we're used to take zero and the naturals up to 10 as the representative of the residues modulo 11.

Tonio