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?
Problem
Source: X International Festival of Young Mathematicians Sozopol 2019, Theme for 10-12 grade
Tags: number theory
Mockhuynh2501
06.10.2019 12:11
Can someone solve this problem?
Pinko
06.10.2019 15:55
Mockhuynh2501 wrote: Can someone solve this problem?
No.
Suppose that $n$ is a composite number and let $p$ be a prime divisor of $n$, such that $p\leq \sqrt{n}$. From the first condition it follows that $q>\sqrt{n}-1\geq p-1$ and since $q$ is prime, we get that $gcd(q,p-1)=1$. Now by Bezout's theorem there exist natural numbers $x$ and $k$, for which $qx=(p-1)k+1$. As $p\mid n$, the second condition gives $a^{n-1}\equiv 1(mod\, p)$, from where
$1\equiv (a^{n-1})^x\equiv(a^{\frac{n-1}{q}})^{qx}\equiv (a^{\frac{n-1}{q}})^{(p-1)k+1}\equiv ((a^{\frac{n-1}{q}})^k)^{p-1}.a^{\frac{n-1}{q}}\equiv a^{\frac{n-1}{q}}\, (mod\, p)$.
Hence $p$ is a common divisor of $a^{\frac{n-1}{q}}-1$ and $n$ which contradicts with the third condition.
MarkBcc168
06.10.2019 16:13
Pocklington Primality Test