0
$\begingroup$

I need to solve a linear congruence:

$17x \equiv 3 \pmod {29}$

The multiplicative inverse is 12. So, multiplying both sides by 12 I get,

$12\cdot 17x \equiv 12 \cdot 3 \pmod{29}$

The next line says :

$x \equiv 36 \pmod{29}$

What is $1 \pmod{29}$ The $12 \cdot 17$ disappears as it is like:

$12 \cdot 17 \equiv 1 \pmod{29}$

How $12\cdot 17$ from the Left Hand Side could be ignored here ?What is the property if $1 \pmod{29}$ that could do this?

$\endgroup$
1

1 Answer 1

1
$\begingroup$

In fact we're working with congruence classes modulo $29$. A congruence class of $x$ modulo $m$ is defined as the set of all numbers that are congruent to $x$ modulo $m$. So for example $[1]_{29}= \{1,30,59,...\}$.

So eventually we have that $[1][x] \equiv [36] \pmod{29}$, as $[12]\cdot [17] = [1]$. Obviously we have that $[1][x] = [x]$, hence we have that $[x] \equiv [36] \pmod {29}$. But as this is an equivalence relation we can say that $x \in [36]_{29}$.

Usually as congruence class representatives are used the numbers from $0$ to $m-1$, so therefore we say that $x$ is congruent to $7$ modulo $29$, but there's nothing wrong saying that $x$ is congruent to $36$ modulo $29$

$\endgroup$
2
  • $\begingroup$ So , [x]<sub>m</sub> means x modulo m ? (Didn't know this notation before ) . Actually , my question is why [1][x] = [x] ? $\endgroup$
    – Utshaw
    Jan 3, 2017 at 9:36
  • $\begingroup$ @Utshaw $[x]_m$ means the set of integers congruent to $x$ modulo $m$. The reason why $[1][x] = [x]$ is that by definition the multiplication of congruence classes is given by $[a][b] = [ab]$ $\endgroup$
    – Stefan4024
    Jan 3, 2017 at 9:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .