Proof by Contradiction with Irrationality and Parity
A proof problem asks you to show that if a and b are positive integers such that a^2 + b^2 is divisible by 3, then both a and b are divisible by 3. A student attempts a proof by contradiction: assume 3 divides a^2 + b^2 but 3 does not divide at least one of a or b. They consider cases: if 3 divides a but not b, then a^2 ≡ 0 mod 3, so b^2 ≡ 0 mod 3, contradiction since b not divisible by 3. If 3 divides neither, then a^2 ≡ 1 mod 3 and b^2 ≡ 1 mod 3, so a^2 + b^2 ≡ 2 mod 3, contradiction. The student concludes the statement is true. You are asked to evaluate the proof for completeness and rigor, and then extend the result to a similar statement modulo 7: if 7 divides a^2 + b^2, must 7 divide both a and b? You need to check whether 7 has the same property as 3, and if not, provide a counterexample.
1. Critique the student's proof for the modulus 3. Is it complete? Are there any missing cases or unjustified steps?
Read the worked answer
The student's proof is essentially correct but needs careful case analysis. The assumption is that 3 | (a^2 + b^2) and not both a and b are divisible by 3. The cases are: (1) 3|a and 3∤b; (2) 3∤a and 3|b; (3) 3∤a and 3∤b. The student covered case (1) and case (3), but did not explicitly cover case (2), which is symmetric to case (1). Also, the student should justify that if 3∤a then a^2 ≡ 1 mod 3. This follows because the nonzero residues mod 3 are 1 and 2, and 1^2=1, 2^2=4≡1. The proof is complete once case (2) is mentioned or dismissed by symmetry. The conclusion that both a and b are divisible by 3 follows by contradiction. So the proof is valid with minor omissions.
2. Investigate the analogous statement modulo 7: if 7 divides a^2 + b^2, must 7 divide both a and b? Either prove it or give a counterexample.
Read the worked answer
The statement is false for 7. Consider a=1, b=2: a^2+b^2=1+4=5, not divisible by 7. Try a=1, b=3: 1+9=10, not divisible by 7. a=2, b=3: 4+9=13, not divisible by 7. a=1, b=5: 1+25=26, not divisible by 7. a=2, b=5: 4+25=29, not divisible by 7. a=3, b=4: 9+16=25, not divisible by 7. a=1, b=6: 1+36=37, not divisible by 7. a=2, b=6: 4+36=40, not divisible by 7. a=3, b=5: 9+25=34, not divisible by 7. a=4, b=5: 16+25=41, not divisible by 7. a=5, b=6: 25+36=61, not divisible by 7. Wait, we need a^2+b^2 ≡ 0 mod 7. The quadratic residues mod 7 are 0,1,2,4. We need two residues summing to 0 mod 7. Possible pairs: (0,0), (1,6) but 6 is not a residue, (2,5) 5 not residue, (4,3) 3 not residue. Actually the only way is both 0? Let's check: residues are {0,1,2,4}. Sums: 0+0=0; 1+? need 6 not in set; 2+? need 5 not in set; 4+? need 3 not in set; 1+1=2; 1+2=3; 1+4=5; 2+2=4; 2+4=6; 4+4=8≡1. So the only pair summing to 0 mod 7 is (0,0). Thus if 7 | a^2+b^2, then a^2 ≡ b^2 ≡ 0 mod 7, so 7|a and 7|b. The statement is actually true for 7. The student's proof for 3 generalizes: for a prime p ≡ 3 mod 4, -1 is not a quadratic residue, so a^2+b^2≡0 mod p implies a≡b≡0 mod p. Since 7 ≡ 3 mod 4, it holds. A counterexample does not exist. The correct extension is to note that the property holds for primes congruent to 3 mod 4, but fails for primes congruent to 1 mod 4, e.g., p=5: 1^2+2^2=5, divisible by 5 but neither 1 nor 2 is divisible by 5.