1
$\begingroup$

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.

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

$$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}$$

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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]$.

$\endgroup$
0
$\begingroup$

$$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.