Equidistant points by modular arithmetic

Question

If $\frac{a}{b}$ is an irreducible rational number, how does one show that the collection of points $\{ \frac{na}{b}\ \mbox{mod}\, 1\}$, $1\leqslant n \leqslant b$ are equidistant along the real line with distance $\frac{1}{b}$?

I’ve tried numerous examples to see how it works but I’m sure how to give a rigorous argument.

Answer 1

$\{\frac {na}b \pmod 1\}, 1⩽n⩽b$ are equidistant along the real line with distance $\frac 1b \iff$

$\{\frac {an}b \pmod 1\} = \{\frac jb \pmod 1|0\le j < b;j\in \mathbb Z\}\iff$

$\{an \pmod b\} = \{j \pmod b\}= \mathbb Z_b\iff$

For all $j$ the equivalence $an \equiv j\pmod b$ is solvable.

Note: If $an \equiv j \pmod b$ is solvable for all $j$ then $an \equiv 1 \pmod b$ is solvable and $a$ is invertable.

And if $a$ is invertible then $an \equiv j\pmod b$ is solvible by $n = ja^{-1}$.

So back to our argument:

For all $j$ the equivalence $an \equiv j\pmod b$ is solvable.$\iff$

$a$ is invertible $\mod b$

Now you should have a theorem that $a$ is invertible $\mod b\iff \gcd(a,b)=1$.

And $\gcd(a,b) = 1 \iff \frac ab$ is an irreducible fraction.

=== old answer below =====

Key thing is that $\gcd(a,b)=1$ so $a$ is invertible $\mod b$ so there is a an integer $k$ so that $ka \equiv 1 \pmod b$, or in other words $ka = 1+ mb$ for some integer $m$, or in other words that $k\frac ab = m + \frac 1b$, or in other words $k\cdot a \equiv \frac 1b \pmod 1$.

And from there it's immediate that for any $0 < j \le b$ we can find that that $(jk)\frac ab \equiv \frac jb \pmod 1$ for all possible $\frac jb$ values.

Remains to show that there are no other possible values.

Well.... if $m\frac ab = \frac {ma}b$ and $ma$ is an integer, so it must be equivalent $\mod b$ to some integer $j: 0\le j < b$. That is if $ma \equiv j \pmod b$ then $ma = j + kb$ for some integer $k$ and $\frac {ma}b = k + \frac jb\equiv \frac jb \pmod 1$.

So as $\frac jb\mod 1$ values will be reached and only $\frac jb\mod 1$ values will be reached.

====

I suppose another way of putting it is

$k \frac ab \equiv \frac jb \pmod 1 \iff ka \equiv j \pmod b$.

And the question becomes a matter of proving if $\gcd(a,b) = 1$ prove that for all residue classes $j$ there will exist a $k$ where $ka \equiv j\pmod b$.

And that is nothing more or less than the basic result: $a$ is invertible $\mod b$ if and only if $\gcd(a,b) =1$.

Answer 2

The key fact here is the notion of invertibility modulo $b$. Firstly, note that you will hit some $c/b$, for $c<b$ iff there exist $n, k$ such that $$ \frac{na}{b} + k = \frac{c}{b} $$

Which is verified iff $$ na +bk = c$$

Here modular arithmetics comes into play. Since $k$ is arbitrary, this is verified if exist $n$ such that $na \equiv c \pmod{b}$. Since $a$ is coprime with $b$, there exist a number $a' $ such that $a a' \equiv 1 \pmod b$, called its inverse modulo b.

Now let's show that we can hit any $c$ we want. By taking $n = ca'$ you will get

$$ na \equiv (ca') a \equiv c (a'a) \equiv c \pmod{b}$$

Yey!

Answer 3

Hint: scaling the fractions by $\,b\,$ yields all the multiples of $\,d := \gcd(a,b)\ $ [by Bezout], i.e.

$$b \underbrace{\!\!\left(\frac{a}b \Bbb Z + \Bbb Z\right)\!\!\!}_{\textstyle\left\{\frac{an}b\!\bmod 1\right\}}\ \, =\, a\Bbb Z + b\Bbb Z\, =\, \gcd(a,b)\, \mathbb{Z} =: d\:\!\Bbb Z\qquad$$

Thus $\,\left\{\dfrac{na}b\bmod 1\right\} =\left\{\dfrac{nd}b\bmod 1\right\} = \left\{ \dfrac{d}b,\ \dfrac{2d}b,\,\ldots,\, \dfrac{b}b\right\} =\, $ multiples of $\,\dfrac{d}b\bmod 1$