Given this modular relation:

$x^3 \equiv y \pmod{3}$

how would you go about proving the transitivity of the system? I have proven the reflexivity, and symmetry pretty easily but the transitivity is giving me many problems, and I feel like im not setting up the problem correctly.


By little Fermat (or directly) note $\,{\rm mod}\ 3\!:\ x^3\equiv x\,$ for all integers $\,x,\,$ thus $\,x^3\equiv y\iff x\equiv y.\,$ Thus your relation is the same as the standard congruence relation '$\equiv$', which is transitive since

$\quad x\equiv y,\ y\equiv z\pmod 3\,\Rightarrow\, 3\mid x\!-\!y,y\!-\!x\,\Rightarrow\, 3\mid x\!-\!y+y\!-\!z = x\!-\!z\,\Rightarrow\,x\equiv z\pmod 3$

Remark $\ $ Note that the inference in the first line already uses the fact that '$\equiv$' is an equivalence relation (transitive, etc). Thus if you don't already know that, then you will need to prove that too (if so, be careful to prove things in the correct order to avoid a circular proof).


It is a more general result that the congruence modulo an integer $p$ relation; $\equiv$; is an equivalence relation on the set of integers. That is, we say that two integers $m$ and $n$ are equivalent modulo $p$ if $p$ divides $m-n$

$$m\equiv n (\mod p)\Leftrightarrow p | (m-n)$$

Pour la transitivité: supposons que $m\equiv n (\mod p)$ and $n\equiv q (\mod p)$ then

$p|m-n$ and $p|q-n$ hence $p|(m-n)-(q-n)=m-q$ This is because if an integer divides two other integers then it divides any linear combination of them, in particular it divides their difference.

So $p|m-q$ which means that $m\equiv q (\mod p)$ hence the relation "$\equiv$ modulo $p$" is transitive.


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.