So many primes!

Number Theory Level 4

How many possibilities are there for the value of $q$ , when:

$p_1^2 + p_2^2 + p_3^2 + \cdots +p_q^2 = c^{q-1}$

where $p_1$ to $p_q$ are any $q$ distinct primes, $c$ is a positive integer and $q$ is a prime of the form $4k+3$ (where $k$ is a positive integer)?

1 0 17 Infinite possibilities

1 solution

Michael Ng
May 21, 2014

Let us work in mod 4. Looking at the LHS, either:

all of the primes are odd, so their squares are all $1 \bmod 4$ , hence the LHS will be $(4k+3) \bmod 4 \equiv 3 \bmod 4$ or,
all of the primes are odd except for one, which is 2, hence the LHS will be $((4k+2)+4) \bmod 4 \equiv 2 \bmod 4$ .

So the LHS can only be 2 or 3 mod 4.

Looking at the RHS, we know that $q-1$ must be even, hence the RHS can be written as $(c^2)^a$ . $c^2$ must be 0 or 1 mod 4, hence $(c^2)^a$ must also be too.

So the RHS can only be 0 or 1 mod 4.

Hence the LHS can never equal the RHS, meaning that there are no solutions for q, giving the answer 0.

I was reading your problem on the brilliant app when I accidentpy pressed the screen and got the wrong answer. Nether the less I get to see a cool solution :)

A Former Brilliant Member - 7 years ago

Thanks Ali!

Michael Ng - 7 years ago

Perfect! My exact method used. :D

Finn Hulse - 7 years ago

@Finn Hulse How can I improve at number theory? Any books you would recommend, I suck at number theory please help.

Mardokay Mosazghi - 7 years ago

When in doubt, take $\mod{4}$ . No just kidding. About NT. I went from Level 2 NT and Level 3 Algebra to Level 5's in both subjects. The key is to look for problems (on Brilliant or in other places) that you can solve, and expand on those areas. Start with basics like the Euclidean algorithm until you get comfortable, then move on to the harder stuff. And get comfortable with modular arithmetic. It's the most useful thing EVER. Keeping an organized mind is another big tip. :D

Finn Hulse - 7 years ago

i use logical thinking :v

Figel Ilham - 6 years, 11 months ago

So many primes!

1 solution

0 pending reports