0

So I want to solve the linear congruence $$17x \equiv 3\mod 29$$

The inverse of $17 (mod 29)$ is 12, from here on, I have no clue how to solve for $x$.

I get the results

$$12*17 \equiv 1\mod29$$ $$12*17x \equiv 36\mod29$$

But I dont understand how to solve of x, could someone please explain?

Arnold Doveman
  • 1,095

2 Answers2

1

$12\times 17x \equiv 36\mod29$

$1\times x \equiv 36\mod29$

$x \equiv 36 \equiv7\mod29$

So, the inverse is used to get rid of the number, in front of $x$. Then, the new number ($36$) at the right-hand side is calculated, modulo $29$

Med
  • 2,530
  • How do you get from the 1st step to the 2nd step, why can you just remove the 1217 coefficient, I know that 1217 is congruent to 1 modulo 29 but what propety are you using? – Arnold Doveman Oct 13 '16 at 12:32
  • Numbers, modulo a prime, make a group under under multiplication. The identity element is 1. So, if a and its inverse are multiplied, they should give the identity, which is 1. Then 1 times x gives x, because 1 is the identity. – Med Oct 13 '16 at 15:32
  • To put it simpler, in modular arithmetic, each number is allowed to be substituted by another number that is in the same group of congruence. So, a.b is substituted by a'.b, where a' is congruent to a. – Med Oct 13 '16 at 15:37
1

We use here one of the arithmetic rules of "$\equiv$", namely: $$ a\equiv b\,(\mathrm{mod}\ m) \Rightarrow ac\equiv bc\,(\mathrm{mod}\ m)\qquad(\ast) $$ for all $c$.

Therefore: if $17x\equiv 3\,(\mathrm{mod}\ 29)$, then by $(\ast)$ $$ 12\cdot 17x\equiv 12\cdot3\,(\mathrm{mod}\ 29). $$ But $17\cdot 12\equiv 1\,(\mathrm{mod}\ 29)$, so by again by $(\ast)$ $17\cdot 12\cdot x\equiv 1\cdot x\,(\mathrm{mod}\ 29)$. Thus $$ 1\cdot x\equiv 12\cdot3\,(\mathrm{mod}\ 29), $$ that is $x\equiv 36\,(\mathrm{mod}\ 29)$. Since $36\equiv 7\,(\mathrm{mod}\ 29)$, it follows that your solution is $x\equiv 7\,(\mathrm{mod}\ 29)$.

boaz
  • 4,783