# Incongruent solutions to $7x \equiv 3$ (mod $15$)

I'm supposed to find all the incongruent solutions to the congruency $7x \equiv 3$ (mod $15$)

\begin{align*} 7x &\equiv 3 \mod{15} \\ 7x - 3 &= 15k \hspace{1in} (k \in \mathbb{Z}) \\ 7x &= 15k+3\\ x &= \dfrac{15k+3}{7}\\ \end{align*}

Since $x$ must be an integer, we must find a pattern for $k$ that grants this. We know that $\frac{k+3}{7}$ must be equal to some integer, say $m$. Solving for $k$, we have $k=4+7m$.

Substituting this into our value for $x$, we get:

\begin{align*} x & = \dfrac{15(4+7m) + 3}{7}.\\ &= \dfrac{63}{7} + \frac{105m}{7}.\\ &= 9+15m. \end{align*}

So, $x = 9+15m, m\in \mathbb{Z}.$

So, is this what I was looking for? I'm not exactly sure what is meant by incongruent solutions.

• Figured it out. Incongruent solutions are solutions that are less than the modulus. In this case, 9 is the only one. – Tyler Murphy Feb 14 '14 at 3:24

$$x = 9+15m, m\in \mathbb{Z}.$$ is the same as $$x \equiv 9 \pmod{15} \,.$$

Equations of the type $ax \equiv b \pmod{n}$ sometimes have no solution, sometimes have one solution $\pmod{n}$ and sometimes they have two or more (incongruent solutions) $\pmod{n}$.

In this case, there is only one, the one you found. A much easier way to find it is to multiply your equation by $2$ and use

$$14x \equiv -x \pmod{15}$$

Let us take your equation $7x=15k+3$ and multiply both sides by $13$.

We get $91x=195k+39$. From where $(6\cdot 15+1)x=15\cdot 13k+2\cdot 15+9$, or what is the same $x=15(13k-6x+2)+9$. Since $k$ was certain integer we could say that $K:=13k-6x+2$ is certain integer and get $x=15K+9$.

So, all solutions leave the same remainder $9$ after division by $15$.

We can solve this congruence equation in elementary way also.

We shall write $[15]$ to denote the word mod 15. Fine?

Note that \begin{align*} &7x\equiv 3[15]\\ -&15x +7x\equiv 3-15[15] ~~\text{because}~~ 15x\equiv 0\equiv 15[15]\\ -&8x\equiv -12[15]\\ &2x\equiv 3\left[\frac{15}{\gcd(15, -4)}\right]~~\text{since}~~ax\equiv ay[m]\Rightarrow x\equiv y\left[\frac{m}{\gcd(a, m)}\right]\\ &2x\equiv 3[15]~~\text{since}~~\gcd(15,-4)=\gcd(15, 4)=1\\ &2x\equiv 3+15[15]~~\text{since} 15\equiv 0[15]\\ &2x\equiv 18[15]\\ &x\equiv 9\left[\frac{15}{\gcd(15, 2)}\right]\\ &x\equiv 9[15] \end{align*}

Thus the solution is given by $x\equiv 9[15]$.

$$\left ( 7,15 \right )=1 \Rightarrow$$ $$x \equiv 3(7)^{^ \phi(15)-1 } (mod 15)$$$$x \equiv 3(7)^{^7}\equiv 3.13 \equiv 9 (mod15)$$, which is the unique solution by Euler-Fermat theorem.