equivalence relations with modular arithmetic

Question

The problem I have to solve is:

Prove an equivalence relation given $\;a\mathcal R b\;$ iff there exists $\;x\in \{1,4,16\}\;$ such that $\;ax\equiv b\pmod{63}\;$

I understand the definitions of reflexive, symmetry and transitive, but i'm not sure how to prove this with the given problem. Could someone please give a hint as to where to start?

Answer 1

Hint $\,\ a\,R\,b \iff b\equiv 4^{\large n} a\pmod{\!63}\, $ for some $\,n\in\Bbb N\ $ (note $\,4^{\large 3}\equiv 1\,\Rightarrow\, 4^{\large -1}\equiv 4^{\large 2}$)

Remark $\ $ This is a special case of oribit equivalence.

Answer 2

Well, start as always: do definition unfolding. I'll show you how to start proving reflexivity:

• Proof goal: $\forall a\in\mathbb{N}. a\ R\ a$

• Proof:

  • Let $a \in \mathbb{N}$.
  • Proof goal now: $a\ R\ a \Leftrightarrow \exists x\in \{1,4,16\}.\quad ax \equiv a$

  • Which $x$ can we take?

    Just take $x = 1$ and we have $a \equiv a$ since $\equiv$ is a eqv. relation and thus reflexive.