Let $k=1,2,\ldots ,n-1$ and $n$ be a positive integer. Define the set $$\begin{align*} A_k&= \{a\ (\text{mod }{n}):k \text{ is the smallest positive integer that satisfies } ka \equiv 0\ (\text{mod }{n})\} \end{align*}$$ Then prove if $k \mid n$ , then $$\begin{align*} |A_k|&= \phi(k) \end{align*}$$ where $|A_k|$ denote the number of elements in $A_k$
I basically have no idea about how to prove this. As so far, by $k \mid n$, I can know that $n =kq$. I can know that $q$ must be the first element in $A_k$, and since we have $ka \equiv 0 \pmod{n}$, so $a=q,2q,3q,\ldots$. But by some examples, I found that the number of possible values of $a$ is just $\phi(k)$.
One example is: let $n=12$, then let $k=6$.
$6 \mid 12$ with $\phi(6)=2$ , and $A_6=\{2,10\}$ . Just like the reasoning above, $12=6 \cdot2$, so $2$ is the first element in $A_6$, then $4=2\cdot2$ can't be an element since $3 \cdot 4=12$ so $k=6$ is not the smallest integer that satisfies $k \cdot 4 \equiv 0 \pmod{12}$. Similarly $6=3\cdot2$, is not in $A_6$ and indeed $6 \cdot6 \equiv 0 \pmod{12}$, but since $2 \cdot6=12$ and $2 \cdot 6 \equiv 0 \pmod{12}$ , so $k=6$ is not the "smallest integer" that satisfies $k \cdot6 \equiv 0 \pmod{12}$, so $6$ is not in $A_6$. By the same reasoning, $8$ is also not in $A_6$. However, $10$ is in $A_6$.
Any help on this?
Fix integer $k$ and $n$, $1\le k\le n-1$.
Suppose $m$ and $a$ are integers, $m>0$ and $a\ge0$. $$ma\equiv0\!\!\!\pmod n \ \iff\ n\mid ma\ \iff\ \frac n{\gcd(n,a)}\mid m$$ Hence the smallest positive integer $m$ that satisfies $ma \equiv 0\! \pmod{n}$ is $\frac n{\gcd(n,a)}$.
Note that if $a=a'\ (\text{mod } n)$, then $\gcd(n,a)=\gcd(n,a')$.
Hence $A_k= \{a \pmod{n}:k=\frac n{\gcd(n,a)}, 0\le a\le n-1\}$
$$\begin{aligned}&k=\frac n{\gcd(n,a)}\\ \iff &\gcd(n,a)=\frac nk\\ \iff &\text{there exists } b\in\Bbb N\text{ such that } a=\frac nkb\text{ and } \gcd(k,b)=1 \end{aligned}$$
Hence $|A_k|=|\{b\in N: 1\le b\le k, \gcd(b,k)=1\}|=\phi(k)$.