Suppose we have $n$ people in a circle $\{0, 1, ..., n-1\}$
Also, suppose we have another person who goes around said circle and gives each of the $n$ people a gift, one each $k$ people, so: \begin{array}{c|c} \mathsf{\text{t}} & \mathsf{\text{Number of people}} \\\hline 0 \strut & 0 \\\hline t_1 \strut& kt_1\mod n \\\hline \end{array}
What would the relations be for the $n, k$ so that every person of the $n$ people get a gift? (The gift giving person has infinite gifts to give).
I have been trying to find a way to find these relations for a while now and can't conclude anything. Tips are welcome.
If the numbers are coprimes, then there is at least one integer $a$ such that: $$a k \mod n = 1 .$$ By the way, $a$ is called the multiplicative inverse of $k$ modulo $n$.
Therefore, for all integers $j$, with $0 \leq j < n$: $$j a k \mod n = j ,$$ Which means that at least by time $t = (n-1) a k$, everyone in the circle will have at least one present.
In fact, I believe it can be proven that at time $t = (n-1) k$ everyone will have exactly 1 present, but I'm struggling with a way to find how to prove it.
If might be helpful to take a look at some information regarding coprime numbers, and to the Chinese remainder theorem.