Prove $|\{a\pmod n:k$ is the smallest positive integer that satisfies $ka \equiv 0 \pmod{n}\}|$ $= \phi(k)$ 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?
 A: $A_k$ is just the set of elements of order $k$.  But in a cyclic group,  there's $\varphi (k)$ elements of order $k$ for each $k$ such that $k\mid n$.
The last statement is relatively easy to prove.   Take a generator,  say $a$:  $\Bbb Z_n=\langle a\rangle. $
Then
$ 1. \lvert a^m\rvert =n/(n,m)$.
You can prove that any subgroup of a cyclic group is cyclic and unique (use a generator).
And then take a generator (for the subgroup of order $k$) and use $1.$
See here for a proof of $1.$
A: 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)$.
