Problem

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

Tags: number theory



The natural number $n>1$ is such that there exist $a\in \mathbb{N}$ and a prime number $q$ which satisfy the following conditions: 1) $q$ divides $n-1$ and $q>\sqrt{n}-1$ 2) $n$ divides $a^{n-1}-1$ 3) $gcd(a^\frac{n-1}{q}-1,n)=1$. Is it possible for $n$ to be a composite number?