First attempt to solve a linear mod equation with one possible solution

Question

This my first concrete attempt to solve a linear mod equation with one answer. I have no idea what I am doing unless I get this right.

$$7x \equiv 6 \pmod{15}$$

$$\gcd(7,15)=1$$

So I know that there is exactly one solution

$7$ times what leaves a remainder of $6$ remainder $1$ when divided by $15$?

In this instance that number is $3$

$21x\equiv18\pmod{15}$

I can rewrite this as $x \equiv 15+6\pmod{15}$

which means $x \equiv 6\pmod{15}$

I figured I could remove the $15$ because we are in $\bmod 15$ which is our "zero"

Answer 1

Solve

$7x\equiv6\pmod{15}$

for unique $x \in \{0,1,2,\dots,14\}$.

You can keep adding $7$ to itself (subtracting $15$ when necessary as you go along) until you get, $\text{modulo } 15$, either

$\quad \;\;\,6\quad$ (Great - I got the answer!)
$\quad \;\;\,1\quad$ (OK, I can work with the inverse of $7$)
$\quad \,14\quad$ (Alright, $-1$ is so 'close' to $1$ I'll find the trick)

$x = 1: 7$
$x = 2: 7 + 7 = 14 = -1$

Now

$\quad 7 \times 2 \equiv -1\pmod{15} \text{ implies } 7 \times 6 \times 2 \equiv -6 \pmod{15} \text{ implies }$ $\quad \quad 7 \times (-6 \times 2) \equiv 6 \pmod{15} \text{ implies } x \equiv -12 \pmod{15} $

So the answer is $x \equiv 3 \pmod{15}$.

Answer 2

There is not just one answer.

Here is how I would find a solution.

$7\cdot 2 \equiv -1\pmod {15}\\ 7\cdot (-12)\equiv 6\pmod {15}\\ -12 \equiv 3 \pmod {15}$

But then anything of the form $3 + 15 k$ would also be a solution.

Answer 3

You could solve this with the Chinese remainder theorem.

$7x\equiv6\bmod15\implies x\equiv0\bmod3$ and $2x\equiv6\bmod5$;

i.e., $x\equiv0\bmod3$ and $x\equiv3\bmod 5$.

Therefore, the solution is $x\equiv3\bmod15$.

Answer 4

You wrote the right thing the first time (although you did the wrong math).

Since you know $\gcd(7,15)=1$, you can realize that $7(-2)+15(1)=1$, so $$7(-2)\equiv 1\pmod{15}$$ Therefore, if you multiply both sides of $$7x\equiv6\pmod{15}$$ by $-2$, you get $$-14x\equiv-12\pmod{15}$$ or $$x\equiv 3\pmod{15}$$

Answer 5

• That number is actually 13
• 18=15+3
• Yes 15 is 0, as is any multiple of it.

$$a\equiv b\pmod m\iff a=mz+b$$ with all variable integers (though z is usually ignored in a lot of cases) or equivalently $$a\equiv b\pmod m\iff a-b=mz$$

so $$7x\equiv 6\pmod {15}\iff 7x=15z+6$$ which means $$7x=(2\cdot 7+1)z+6$$ which then follows to $$7(x-2z)=z+6$$ which is solved by $z=1$ as well as adding ( or subtracting) any multiple of 7 ( so 8,15,...) . plugging the smallest positive value, gives $7x-14=7$ which has solution $x=3$ they actually have gaps of 7.

Anyways, back to your version (with mod 15), $$13\cdot 7=6\cdot 15+1$$ so multiplying by 13 we have $$91x\equiv 78\pmod {15}$$ giving ( on reduction ) $$x\equiv 3\pmod {15}$$

Answer 6

Since $(7, 15)=1$, there's an inverse for $7\pmod{15}$. It's $-2$, since $-2\cdot7+1\cdot15=1$. That is, $-2\cdot7\cong1\pmod{15}$.

You can use Euclid's algorithm to find the inverse, rather than pulling a rabbit out of a hat.

Once you have the inverse, the problem resembles an algebra l exercise. The only difference is that everything is $\pmod{15}$.

Thus $7x\cong 6\pmod{15}\implies x\cong7^{-1}\cdot6\pmod{15}\implies x\cong-2\cdot6\pmod{15}\implies x\cong-12\pmod{15}\implies x\cong3\pmod{15}$.