In Abstract Algebra by Hungerford, Problem 11 (c) page 29 is as follows:
Find all solutions for the following congruence:
6x = 9 (mod 15)
Can anyone help me solve this congruence. What is the method or approach?
Bernhard
In Abstract Algebra by Hungerford, Problem 11 (c) page 29 is as follows:
Find all solutions for the following congruence:
6x = 9 (mod 15)
Can anyone help me solve this congruence. What is the method or approach?
Bernhard
If x is solution of the 'congruence equation'...
$\displaystyle 6 x \equiv 9\ \text{mod}\ 15$ (1)
... then must be...
$\displaystyle 6\ x = k\ 15 +9 \implies x= \frac{5\ k + 3}{2}$ (2)
Now the (2) is verified for...
$\displaystyle k=1 \implies x=4$
$\displaystyle k=3 \implies x=9$
$\displaystyle k=5 \implies x=14$
... so that the (1) has three solutions...
Kind regards
$\displaystyle \chi$ $\displaystyle \sigma$
Notice that the solutions, x= 4, 9, and 14, to 6x= 9 (mod 15) so NOT satisfy 2x= 3 (mod 15) but do satisfy 2x= 3 (mod 5). That is because the equation ChiSigma got, 6x= 9+ 15k, is the same as 2x= 3+ 5k.
Another way to solve the Diophantine equation, 2x- 5k= 3, useful for problem where the modulus is too large to conveniently "try" integer values for k, is to note that 2 divides into 5 twice with remainder 1. That is, 5(1)- 2(2)= 1 so that 2(-2)- 5(-1)= 1 and then, multiplying by 3, 2(-6)- 5(-3)= 3. That is, one solution is x= -6, k= -3. But notice that is we replace x with x+ 5n and y with y+ 2n, we have 2(x+ 5n)- 5(k+ 2n)= 2x+ 10n- 5k- 10n= 2x- 5k which equals three if and only if x and k satisfy the equation. That is, all solutions are of the form x= -6+ 5n. In particular, taking n= 2 3, and 4 give x= 4, 9, and 14, the three solutions between 0 and 15.
Unlike the congruence equation of the OP, both the congruence equations $\displaystyle 2\ x \equiv 3\ \text{mod}\ 15$ and $\displaystyle 2\ x \equiv 3\ \text{mod}\ 5$ have only one solution...
a)
$\displaystyle 2\ x \equiv 3\ \text{mod}\ 15$ (1)
The multiplicative inverse of $\displaystyle 2\ \text{mod}\ 15$ is $\displaystyle 8$ so that if we multiply both terms of (1) by 8 we obtain $\displaystyle x= 9\ \text{mod}\ 15$ ...
b)
$\displaystyle 2\ x \equiv 3\ \text{mod}\ 5$ (2)
The multiplicative inverse of $\displaystyle 2\ \text{mod}\ 5$ is $\displaystyle 3$ so that if we multiply both terms of (1) by 3 we obtain $\displaystyle x= 4\ \text{mod}\ 15$ ...
It is easy to verify that there are no more solutions neither for (1) nor for (2)...
Kind regards
$\displaystyle \chi$ $\displaystyle \sigma$