How many natural numbers between $2$ and $60$ have no primitive roots and require at least four squares to be expressed as a sum of squares?

Question

A natural number $n$ is called individual if $n$ has no primitive roots and at least $4$ squares are needed so that it is expressed as a sum of squares. How many natural numbers $n$ between $2$ and $60$ are there that are individual?

I have thought to use the following theorem:

Theorem. An integer $n \geq 2$ has a primitive root if and only if it is one of the following: $2, 4, p^a, 2p^a$, where $p$ is prime, $p\neq2$, and $a\geq1$.

But the natural number $n$ needs to be of the form $n=x^2+y^2+z^2+w^2$.

How can we find how many $n$ there are that can be written as a constant multiplied by a power of a prime number?

Answer 1

Things which force a natural number to not be individual:

• being $2$ or $4$,
• being a power of an odd prime,
• being twice a power of an odd prime,
• being a square,
• being representable as the sum of two squares, equivalently, by the sum of two squares theorem, not having any of its prime factors which are congruent to $3 \pmod{4}$ appear to an odd power, or
• being representable as the sum of three squares, equivalently, by Legendre's three-square theorem, not being of the form $4^a(8b+7)$ for nonnegative integers $a$ and $b$.

So the following are not individual in $[2, 60]$:

• $2$ and $4$;
• the powers of odd primes, $3, 9, 27$, $5, 25$, $7, 49$, $11$, $13$, $17$, $19$, $23$, $29$, $31$, $37$, $41$, $43$, $47$, $53$, and $59$;
• the twice powers of odd primes, $6, 18, 54$, $10, 50$, $14$, $22$, $26$, $34$, $38$, $46$, and $58$;
• the squares, $1$, $4$, $9$, $16$, $25$, $36$, and $49$; and
• not having an odd power of a $3 \pmod{4}$ prime, $8$, $20$, $32$, $40$, $45$, and $52$.

This only leaves $17$ canddiates. For each, pulling out the largest power of $4$ and writing the resulting cofactor by the division algorithm with divisor $8$, this leaves (underlining those with remainder $7$ in the division): \begin{align*} 12 &= 4^1 \cdot (0 \cdot 8 + 3) \text{,} \\ 15 &= 4^0 \cdot (\underline{1 \cdot 8 + 7}) \text{,} \\ 21 &= 4^0 \cdot (2 \cdot 8 + 5) \text{,} \\ 24 &= 4^1 \cdot (0 \cdot 8 + 6) \text{,} \\ 28 &= 4^1 \cdot (\underline{0 \cdot 8 + 7}) \text{,} \\ 30 &= 4^0 \cdot (3 \cdot 8 + 6) \text{,} \\ 33 &= 4^0 \cdot (4 \cdot 8 + 1) \text{,} \\ 35 &= 4^0 \cdot (4 \cdot 8 + 3) \text{,} \\ 39 &= 4^0 \cdot (\underline{4 \cdot 8 + 7}) \text{,} \\ 42 &= 4^0 \cdot (5 \cdot 8 + 2) \text{,} \\ 44 &= 4^1 \cdot (1 \cdot 8 + 3) \text{,} \\ 48 &= 4^1 \cdot (1 \cdot 8 + 4) \text{,} \\ 51 &= 4^0 \cdot (6 \cdot 8 + 3) \text{,} \\ 55 &= 4^0 \cdot (\underline{6 \cdot 8 + 7}) \text{,} \\ 56 &= 4^0 \cdot (7 \cdot 8 + 0) \text{,} \\ 57 &= 4^0 \cdot (7 \cdot 8 + 1) \text{, and} \\ 60 &= 4^1 \cdot (\underline{1 \cdot 8 + 7}) \text{.} \\ \end{align*} Therefore, the individual numbers in the given interval are $15$, $28$, $39$, $55$, and $60$.