WordGPT

No number 4k + 3 is a sum of two squares

Exercise · Level 3 (Medium)

Prove that a number leaving remainder 3 when divided by 4 (like 2027) cannot be written as a² + b².

a2+b2≢3(mod4)a^2+b^2\not\equiv3\pmod4

wordgptpro.com

Solution

  1. An even number squared is (2m)2=4m2≡0(2m)^2=4m^2≡0, an odd number squared is (2m+1)2=4(m2+m)+1≡1(2m+1)^2=4(m^2+m)+1≡1 (mod 4). So squares leave remainder 0 or 1.

  2. A sum of two squares then leaves remainder 0+0, 0+1, 1+1=0,1,20+0,\ 0+1,\ 1+1=0,1,2. The remainder 3 never occurs:

    a2+b2≡0,1 or 2(mod4)a^2+b^2\equiv0,1\text{ or }2\pmod4
    (1)
  3. Since 2027=4⋅506+32027=4\cdot506+3, the number 2027 is not a sum of two squares.

Answera2+b2≠4k+3a^2+b^2\ne4k+3

wordgptpro.com

Need a hint?

What remainders can a square leave when divided by 4?

Squares leave remainder 0 or 1 modulo 4, so a sum of two squares never leaves 3; in particular 2027 is not a sum of two squares.

How to work it out

  1. An even number squared is (2m)2=4m2≡0(2m)^2=4m^2≡0, an odd number squared is (2m+1)2=4(m2+m)+1≡1(2m+1)^2=4(m^2+m)+1≡1 (mod 4). So squares leave remainder 0 or 1.

  2. A sum of two squares then leaves remainder 0+0, 0+1, 1+1=0,1,20+0,\ 0+1,\ 1+1=0,1,2. The remainder 3 never occurs:

    a2+b2≡0,1 or 2(mod4)a^2+b^2\equiv0,1\text{ or }2\pmod4
    (1)
  3. Since 2027=4⋅506+32027=4\cdot506+3, the number 2027 is not a sum of two squares.

LaTeX source of the formulas on this page
\[ a^2+b^2\ne4k+3 \]
\[ a^2+b^2\equiv0,1\text{ or }2\pmod4 \]

Questions

What is the answer to: No number 4k + 3 is a sum of two squares?

Squares leave remainder 0 or 1 modulo 4, so a sum of two squares never leaves 3; in particular 2027 is not a sum of two squares.

What is the key idea?

Check the possible remainders of a square modulo 4.

Is there a hint?

What remainders can a square leave when divided by 4?

Related problems

More number theory problems

    No number 4k + 3 is a sum of two squares: answer and solution | WordGPT