1

The theorem is

There are m numbers: $$\text{0 mod m, n mod m, 2n mod m, ..., (m - 1)n mod m}$$ consist of precisely $d$ copies of the $m/d$ numbers $$0, d, 2d, ..., m - d$$ in some order, where $d = gcd(m, n)$. For example, when m = 12 and n = 8 we have d = 4, and the numbers are 0, 8, 4, 0, 8, 4, 0, 8, 4, 0, 8, 4.

Then it starts proving as follows

The first part of the proof - to show that we get d copies of the first m/d values - is now trivial. We have $$jn \equiv kn\ (mod\ m) \iff j(n/d) \equiv k(n/d)\ (mod\ m/d)$$ hence we get d copies of the values that occur when $0 \le k \lt m/d$

  • What are j and k in the above equation ?
  • How that equation tells that there are d copies of the values that occur when $0 \le k \lt m/d$ ?

In the next page it goes on proving the second part of the theorem and says

The m numbers are distinct when $m \perp n$ because $$jn \equiv kn\ (mod\ m) \iff j \equiv k\ (mod\ m)$$

  • how this equation implies the numbers are distinct ?
Jean Marie
  • 81,803
Abhisek
  • 465

1 Answers1

3

We want to prove that the following sequence: $$0, 1n, 2n, ... , (m-1)n \; (mod\; m)$$

Is equal to the sequence:$$0,d,2d, ... ,(m'-1)d$$ In some order, repeated $d$ times. Where $d=gcd(m,n)$.

Assume $m=dm'$ and $n=dn'$. They do it in two steps:

1) Prove that the sequence $0, 1n, 2n, ... , (m-1)n \; (mod\;m)$ is formed by $d$ equal subsequences of length $m'$ ('concatenated').

2) Each subsequence is formed by $m'$ different multiples of $d$ - from $0d$ to $(m'-1)d$ - in some order.

So, first, they state that:

(Identity 1) $$jn=kn \;(mod\;m) \iff jn'= kn'\; (mod\;m')$$ Hence we get $d$ copies of the values that occur when $0≤k<m'$

Which is your first doubt. Notice that when we equate $jn$ and $kn$, we are loooking for different multiples of $n$ which have the same value $(mod\;m)$ (and thus mapping groups of multiples of n to the possible residues $(mod\; m)$, which is our subject)

So - let $j=im'+k$. Then: $$kn'=(im'+k)n' \;(mod\; m')$$

Note that the value of $i$ doesn't matter in this equation, since $im'=0 \;(mod\; m')$. So, it follows that, for a fixed $k$ , $0 \leq k \leq (m'-1)$ (which are all possible values of residues $(mod\;m')$) , all of the following hold:

$$kn'=(0m'+k)n'=(1m'+k)n'=(2m'+k)n'\; ... \; (mod \; m')$$

And all $j=(im'+k)$ here are the same $(mod\; m')$ (they are equal to $k$).

And, because of the $Identity \;1$, these equalities with $j$ and $k$ also hold for multiples of $n\;(mod\;m)$, but, this time, $im'$ is not 0 in the modulus, except if $i=zd$, which makes the values of $j$ for each $k$ to have a cycle of length $d$ when varying $i$, because:

$$ kn=(0m'+k)n =(1m'+k)n =(2m'+k)n, ... =((d-1)m'+k)n \;(mod\;m)$$

$$ kn=(dm'+k)n=(0m'+k)n \; (mod\;m)$$ $$ kn=((d+1)m'+k)n=(dm'+m'+k)n=(m'+k)n=(1m'+k)n' \; (mod\;m)$$ $$ kn=((d+2)m'+k)n=(dm'+2m'+k)n=(2m'+k)n \; (mod\;m)$$

And so on.

So - for each $0 \leq k \leq (m'-1)$ we have $d$ values $((0m'+k)n, (1m'+k)n .. ((d-1)m'+k)n, )$ for which the residue $mod\;m$ is the same. Note that it covers all possible residues $mod\;m$ (since there are $m'$ residues repeating $d$ times each, $m'd=m$). So we just have to examine th values for $0\leq k \leq (m'-1)$, because it repeats. Thats the first point made and step 1.

Then it states that, by distributivity, $(kn\; mod\; m)=d(kn'\; mod\; m')$. This statement is 'all $(kn\; mod\; m)$, the multiples of $n\; mod\; m$ (which are the numbers we are searching), are equal to $d$ multiplied by $(kn'\; mod\; m')$'. So we already know, besides step 1, that the numbers we want, $0n,1n, 2n ..(m-1)n$, are equal to $dkn'$. That is: $$(0n \;mod\; m) = d(0n'\; mod \;m')$$ $$(1n \;mod\; m) = d(1n'\; mod\; m')$$ $$(2n\; mod \;m) = d(2n' \;mod\; m')$$ $$ ...$$ $$((m'-1)n\;mod\;m) = d((m'-1)n'\; mod \;m')$$

So, all we have to do now is to show that the values $(0n'\;mod\; m'),(1n'\; mod\ m').., ((m'-1)n'\; mod\; m')$ are different from each other - because they are $m'$ in quantity and there are only $m'$ possible values of residues $mod\;m'$ - so each one of them would assume one possible value of residue (and thus we would have $0d,1d,.(m'-1)d$) . And this is shown using the following fact:$$if\; gcd(m',n')=1 \; then\; jn'=kn'\; (mod\;m') \iff j=k\; (mod\; m')$$

That is - if $m'$ and $n'$ are coprime (which they are, since we divided both by their gcd), two multiples of $n'\;(mod\;m')$ are equal if and only if the multipliers themselves are equal $mod\;m'$. Since the literal values of the multipliers here are all less than $m'$,they can't be equal $mod\;m'$ (the only possibility of equality would be something like $k=(im'+j)$ with $i \geq 1$, like stated before). Thats step 2.

galmeida
  • 151