A class of n children sit in a circle. The teacher walks around the outside of the circle and pats every kth child on the head. Find and prove a necessary and sufficient condition on n and k for every child to receive a pat on the head.
I don't know if the first part of the proof is clear enough and if $znx + zky = z$ justifies that every child gets a pat. What are something that I can add to make this clearer?
The sufficient and necessary condition for every child to receive a pat on the head would be that $n$ and $k$ are relatively prime.
Hence, given the conditions that there are $n$ children in the class, and the teacher pats every $k$th student on the head, we will need to prove that every child will receive a pat on the head if and only if $n$ and $k$ are relatively prime.
To prove the statement that every child will receive a pat on the head if and only if $n$ and $k$ are relatively prime, we need show that the following two parts are true:
First we need to show that if $n$ and $k$ are relatively prime, every child will receive a pat. If $n$ and $k$ are relatively prime, their greatest common divisor is 1, which means that there are integers $x$ and $y$ such that $nx + ky = 1$. Let $z$ be an integer between 1 and $n$, multiplying each side of the equation by z, we get $znx + zky = z$. Hence, the $z$th child will get a pat on the head on $zy$th pat after the teacher walked $zx$ times around the circle. $z$ could be set to any number between 1 and $n$ and $zx$, $zy$ will yield distinct results for different $z$. Therefore, every child will get a pat on the head.
Secondly, we will prove that if every child gets a pat, $n$ and $k$ are relatively prime by contradiction. Suppose every child gets a pat, and that $n$ and $k$ are not relatively prime. Then, $gcd(n, k) \ne 1$. Let $x$ be the greatest common divisor of $n$ and $k$. Thus $x$ divides both $n$ and $k$, which means that there are integers $a$, $b$ such that $n = xa$ and $k = xb$. Since $k = xb$, multiples of k can be written as $ck= cxb$ for some constant $c$ and all the multiples of $k$ are multiples of $x$. It would imply that only children who are seating at the places of $x$ modulo $n$ will get a pat.
We know that $n$th child will get a pat because $n = xa$. Since $xa$ and $cxa + 1$ are relatively prime for all integers $c$, the first child cannot get a pat since the first child sits next to the $n$th child, who gets a pat. However, this is a contradiction with the supposition that every child, including the first child, will get a pat. Therefore, if every child gets a pat, $n$ and $k$ are relatively prime.
Therefore, every child will receive a pat on the head if and only if $n$ and $k$ are relatively prime.