# Math Help - Modular arithmetic ; Solutions to 6x = 9 (mod 15)

1. ## Modular arithmetic ; Solutions to 6x = 9 (mod 15)

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

2. ## Re: Modular arithmetic ; Solutions to 6x = 9 (mod 15)

If x is solution of the 'congruence equation'...

$6 x \equiv 9\ \text{mod}\ 15$ (1)

... then must be...

$6\ x = k\ 15 +9 \implies x= \frac{5\ k + 3}{2}$ (2)

Now the (2) is verified for...

$k=1 \implies x=4$

$k=3 \implies x=9$

$k=5 \implies x=14$

... so that the (1) has three solutions...

Kind regards

$\chi$ $\sigma$

3. ## Re: Modular arithmetic ; Solutions to 6x = 9 (mod 15)

Thanks for the help

Peter (Math Hobbyist)

4. ## Re: Modular arithmetic ; Solutions to 6x = 9 (mod 15)

Another version: solve the equation $\bar{6}\bar{x}=\bar{9}$ in $\mathbb{Z}_{15}=\{\bar{r}:r=0,1,\ldots,14\}$ .

5. ## Re: Modular arithmetic ; Solutions to 6x = 9 (mod 15)

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.

6. ## Re: Modular arithmetic ; Solutions to 6x = 9 (mod 15)

Originally Posted by HallsofIvy
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 $2\ x \equiv 3\ \text{mod}\ 15$ and $2\ x \equiv 3\ \text{mod}\ 5$ have only one solution...

a)

$2\ x \equiv 3\ \text{mod}\ 15$ (1)

The multiplicative inverse of $2\ \text{mod}\ 15$ is $8$ so that if we multiply both terms of (1) by 8 we obtain $x= 9\ \text{mod}\ 15$ ...

b)

$2\ x \equiv 3\ \text{mod}\ 5$ (2)

The multiplicative inverse of $2\ \text{mod}\ 5$ is $3$ so that if we multiply both terms of (1) by 3 we obtain $x= 4\ \text{mod}\ 15$ ...

It is easy to verify that there are no more solutions neither for (1) nor for (2)...

Kind regards

$\chi$ $\sigma$

7. ## Re: Modular arithmetic ; Solutions to 6x = 9 (mod 15)

Thanks again for the help

Peter