Recall that for an arbitrary prime p, we define a primitive root modulo p as an integer r for which the least positive integer v such that r^{v}\equiv 1\pmod{p} is p-1. Prove or disprove the following statement: For every prime p>2023, there exists positive integers 1\leqslant a<b<c<p such that a,b and c are primitive roots modulo p but abc is not a primitive root modulo p.
Problem
Source: Thailand TSTST 2024 P3
Tags: number theory, primitive root
Tkn
18.07.2024 19:16
EDIT: Thanks to @below. Yeah, I think that's how this problem is intended.
Try consider p=2^{16}+1 is a prime, take one primitive root called g. Notice that every primitive root must congruent to g^k\pmod{p} where k is an odd integer.
vsamc
18.07.2024 22:28
I interpret the statement as "Determine the truth of the statement for each prime p\geq 2023." I don't think @above interpreted it the same way, but either way it's basically the same thing.
The statement is only true if p is not a Fermat prime, i.e. p \neq 2^{2^n}+1 for any positive integer n.
Writing a \equiv g^x, b \equiv g^y, c \equiv g^z \pmod{p} for some primitive root g and integers x,y,z, we see that the statement is equivalent to the following: Do there exist integers x, y, z such that \gcd(x, p-1) = \gcd(y, p-1) = \gcd(z, p-1) = 1 such that \gcd(x+y+z, p-1) > 1? And now, I claim that this is true if and only if p is not a Fermat prime.
First, assume that p was not a Fermat prime. Then, there exists an odd prime q dividing p-1. Choose x\equiv 1\pmod{q}, y\equiv 1\pmod{q}, z\equiv -2\pmod{q}, and x, y, z \equiv 1\pmod{\frac{p-1}{q^{\nu_q(p-1)}}} (we can do this by CRT). Then, the gcd condition is upheld, but x+y+z\equiv 0\pmod{q}, so q\mid \gcd(x+y+z, p-1), so \gcd(x+y+z, p-1) > 1. Thus, it is possible when p is not a fermat prime.
If p is a fermat prime, then p-1 = 2^{2^n}, and so the gcd condition is equivalent to x,y,z being odd. Then, x+y+z is also odd, so we must necessarily have \gcd(x+y+z, p-1) = 1. So it is not possible when p is a fermat prime.
Thus, we've characterized all such p for which this works, as desired. \blacksquare
hexapr353
18.07.2024 23:42
Fun fact: If the constant 2023 has been changed with another constant bigger than 65537 then this problem would be equivalent to an open conjecture.