Let n>1 be a natural number such that there is a natural number a and a prime number q for which the following conditions are satisfied:
q divides n-1 and q>sqrt(n) - 1
n divides a^(n-1)-1
The greatest common factor of a^((n-1)/q)-1 and n is 1.
Isnit possible for n to not be prime.
Hi, this is a problem from a Romanian competition, but because I'm quite bad at number theory I wasn't able to either solve it or make any significant progress. I will appreciate any solutions. Thank you in advance!
With any $a$ where $n \mid a^{n-1} - 1$, let its multiplicative order be
$$k = \text{ord}_n(a) \tag{1}\label{eq1}$$
In particular, $k$ is the smallest positive integer such that $a^k \equiv 1 \pmod n$. Then $k$ must divide $n - 1$ and, as stated in the Properties section of Wikipedia's "Multiplicative order" article, $k$ also divides Euler's totient function, i.e., $\varphi(n)$.
If $\gcd(k,q) = 1$, then $k \mid \frac{n-1}{q}$, so $n \mid a^{\frac{n-1}{q}} - 1$, which is not allowed based on the stated conditions. Thus, $q \mid k$ and since $k \mid \varphi(n)$, then $q \mid \varphi(n)$. Next, note Euler's product formula gives
$$\varphi (n)=n\prod_{p\mid n}\left(1-{\frac {1}{p}}\right) \tag{2}\label{eq2}$$
where the product is over the distinct prime numbers dividing $n$. Since $q \mid n - 1$, it can't be a factor of $n$ and, thus, it must be a factor of one of the numerators of the $\frac{p-1}{p}$ factors, i.e., there exists at least one specific prime $p$ where $q \mid p - 1$.
If it's assumed $n$ is composite, you can easily verify no such $n \lt 9$ works, so since $q \gt \sqrt{n} - 1$, then $q$ must be an odd prime. Thus, the prime $p$ where $q \mid p - 1$ must be of the form $p = 2mq + 1$ for some positive integer $m$. Also, as $n$ is assumed to be composite, there must be at least $1$ other prime factor. Since $n \equiv 1 \pmod q$ and $p = 2mq + 1 \equiv 1 \pmod q$, then $\frac{n}{p} \equiv 1 \pmod q$, so $\frac{n}{p} = jq + 1$ for some positive integer $j$. This means that $n = (2mq + 1)(jq + 1) = 2jmq^2 + (j + 2m)q + 1$, giving $\sqrt{n} \gt \sqrt{2jm}q \gt q + 1$. Thus, $q \lt \sqrt{n} - 1$, contradicting the condition of $q \gt \sqrt{n} - 1$. As such, the assumption that $n$ is composite can't be true and, thus, $n$ must be prime.