28th Hellenic Mathematical Olympiad

(a) Let $3\nu +1=7\kappa$, where $\nu ,\kappa \in \mathbb{Z}$. The integer $\nu$ is of the form $\nu =7\rho +\upsilon$, where $\upsilon \in \{0,1,2,3,4,5,6\}$ and $\rho \in \mathbb{Z}$. Then we have: $$3(7\rho +\upsilon )+1=7\kappa \iff 21\rho +3\upsilon +1=7\kappa \iff 3\upsilon +1\equiv 0(\mathrm{mod}7)$$ and hence the possible value for $\upsilon$ is $2$. Thus we have $\nu =7\rho +2$, where $\rho \in \mathbb{Z}$, and the remainder of the division of $\nu$ by $7$ is $2$.

(b) We have $${\nu }^m=(7\rho +2{)}^m=\sum _{i=0}^m(\genfrac{}{}{0ex}{}{m}{i})(7\rho {)}^{m-i}{2}^i=\text{multiple of }7+2^m.$$ Therefore it is enough to find the remainders of the division of $2^m$ by $7$. If $m=3\sigma +\upsilon$, where $\upsilon \in \{0,1,2\}$, then we get: $$2^m=2^{3\sigma +\upsilon }=8^{\sigma }\cdot 2^{\upsilon }=(7+1{)}^{\sigma }\cdot 2^{\upsilon }=(\text{multiple of }7+1)\cdot 2^{\upsilon }=\text{multiple of }7+2^{\upsilon },$$ where $\upsilon \in \{0,1,2\}$. Hence the possible remainders of the division of ${\nu }^m$ by $7$, for all values of the positive integer $m$ are $2^0=1$, $2^1=2$, and $2^2=4$.