lin_cong
PDF · 2 pages · 65.2 KB
Open PDF file
Notes from the Galois Book update files (July 2013) on solving linear congruences. Theorem 1 shows a unique solution mod m when (a,m)=1, constructed from sa+tm=1. Theorem 2 shows a solution exists iff gcd(a,m) divides b, gives the g solutions u0+jm/g, and includes proofs and examples such as 5x≡1 (mod 15) and 42x≡12 (mod 78).
AI-written summary; may contain errors.
Extracted text (machine-read; may contain errors)
Linear Congruences axbmodm
Theorem 1.If(a;m) = 1 , then the congruence axbmodmphas exactly one solution
modulom.
Constructive. Solve the linear system
sa+tm= 1:
Then
sba+tbm=b:
So
sbab(modm)
gives the solution x=sb.
Ifu1andu2are solutions, then
au1b(modm) andau2b(modm)
=)au1au2(modm)
=)u1u2(modm) since (a;m) = 1:
So there is only one solution.
Example 1. 3x50 (mod 113)
Note thataxb(modm) impliesax=b+qmfor some integer q. So a common divisor of
a;m also divides b.
Example 2. 5x1 (mod 15) is not solvable.
Theorem 2.Consider the congruence axb(modm).
1. The congruence has a solution if and only if (a;m)jb.
2. Ifu0is any particular solution, then a complete set of solutions is:
u0;u0+m
g;u0+2m
g;:::;u 0+(g 1)m
g
whereg= (a;m). Thus there are gsolutions.
3. A particular solution u0can be obtained by solving the congruence
a
gxb
g(modm
g)
This is possible since a
g;m
g
= 1. (See last theorem.)
Example 3. 42x12 (mod 78)
2
Proof.
1. Ifaxb(modm) has a solution and g= (a;m), then clearly gjb.
3. Suppose g= (a;m) andgjb.
Then
a
g;m
g
= 1. So we can nd a u0such that
a
gu0b
g(modm
g)
Therefore,au0b(modm).
2. Suppose u0is a solution. Then
u=u0+tm
g
=)au=au0+atm
g
=)au=au0+a
gtm
=)au=au0(modm)
=)au=b(modm):
Souis a solution.
Suppose, on the other hand, that uis a solution. Then
auau0b(modm)
=)a(u u0)0 (modm)
=)a
g(u u0)0 (modm
g)
=)u u00 (modm
g)
=)u u0=tm
g:
Letjt(modg) where 0jg 1. Then
tm
gjm
g(modm)
=)u u0jm
g(modm)
=)uu0+jm
g(modm);
where 0jg 1.
It is easy to check that no two of the numbers u0+jm
g(0j < g ) are congruent
modulom.