Problem

Source: VI International Festival of Young Mathematicians Sozopol, Theme for 10-12 grade

Tags: number theory, prime numbers, Divisibility



Let $p$, $q$ be two distinct prime numbers and $n$ be a natural number, such that $pq$ divides $n^{pq}+1$. Prove that, if $p^3 q^3$ divides $n^{pq}+1$, then $p^2$ or $q^2$ divides $n+1$.