Wlog let $a_i=i$ and $b_i=f(i)$ with $f:\mathbb{Z}/n\mathbb{Z}\rightarrow \mathbb{Z}/n\mathbb{Z}$ being a bijection. Assume $p^k|n$ and $p^k|x$. Since $\{if(i)\}\equiv\{i\}\pmod{n}$ (otherwise we are trivially done by PHP), reducing $\pmod{p^k}$ gives us that the multiset $\{if(i)\}$ contains $\frac{n}{p^k}$ $1$s,...,$\frac{n}{p^k}$ $p^k$s. Assume there is a $y$ with $p^k\nmid y$ such that $mp^k=x=f(y)$. This means that there are at least $\frac{n}{p^k}+1$ numbers divided by $p^k$: $1p^kf(1p^k),..., \frac{n}{p^k}{p^k}f(\frac{n}{p^k}p^k), yf(y)=yx\equiv 0\pmod{p^k}$, but this would be a contradiction with what we found earlier. Therefore, by looking at the various primes, and noticings that we can also conversely say $p^k|n, f(x)\implies p^k|x$, we have $(x;n)=(f(x);n)$. In particular this means that, if $v_p(n)=k>0$, the set $\{i| p\nmid i\}$ gets mapped to itself through the function $xf(x)$. Therefore, looking at the product, we must have, if $p$ is odd, $-1\equiv\prod_{p\nmid i} i\equiv\prod_{p\nmid i}if(i)=(\prod_{p\nmid i} i)^2\equiv(-1)^2=1\pmod{p^k}$, where the first and last equivalences come from the same proof of Wilson's theorem (there's only one $x\neq 1$ such that $x\equiv \frac{1}{x}$ which is $-1$, and so pairing reciprocal terms the product is $-1$), so we have a contradiction. The only case left is $n=2^k$ with $k>1$ but the numbers with $(n;2^k)=2^{k-1}$ and those with $(n;2^k)=2^k$ must map to themselves, but this means $f(2^{k-1})=2^{k-1}$ and $f(2^k)=2^k$. This however is a contradiction since $2^k|2^{k-1}2^{k-1}-2^k2^k$ if $k>1$, and so we are done.

umedkarimov wrote: Problem 5. Consider an integer number $n>2.$ Let $a_1,a_2, \ldots, a_n$ and $b_1,b_2,\ldots,b_n$ be two permutations of $0,1,2,\ldots,n-1.$ Prove that there exist some $i\neq j$ such that: $$n \mid a_i b_i-a_j b_j.$$