How do we proof this in integers modulo n.

30 Views Asked by At

Let's say we have four integers, $\phi$, $\theta$, $\omega$ and $\zeta$. Where we define $\omega$ and $\zeta$ to be co-prime.

What I have to show (or prove?) is the following statement:

The equivalence classes of R match with the elements of the integers modulo $\zeta\omega$. Where with 'integers modulo cd' I mean: $\mathbb{Z}_{\zeta\omega}=\{[0], [1], ..., [\zeta\omega-1]\}$ (The set of the equivalence classes)

This means:

The equivalence class of $\phi$ under $R$ is the same as the equivalence class of $\phi$ in $\Bbb Z_{\zeta\omega}$.

I am absolutely clueless as to how I should approach this proof.


1

There are 1 best solutions below

1
On BEST ANSWER

Let's look at a specific example. Take a couple of primes for $c,d$. I suggest small ones like $2$ and $3$ so there are not many cases. The equivalence classes of $\Bbb Z_6$ are then $[0],[1],[2],[3],[4],[5]$. Now see what integers are in the same equivalence class with $0$ under $R$. It turns out they are the same ones as in the class for $\Bbb Z_6$. What you are trying to show is $$aRb \iff (b-a) \equiv 0 \bmod 6 \iff (b-a) \in [0_6]$$ or the same with $6$ replaced by $cd$. The first comes from your definition of $R$, the second from the definition of $[0_{cd}]$

Your statement "This means" should say "the equivalence class of $a$ under $R$ is the same as the equivalence class of $a$ in $\Bbb Z_{cd}$