Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This Wikipedia article of Infinite Descent says:

We have $ 3 \mid a_1^2+b_1^2 \,$. This is only true if both $a_1$ and $b_1$ are divisible by $3$.

But how can this be proved?

share|improve this question
1  
Do you know modular arithmetic? The only squares modulo three are zero and one, and so the sums of two squares can only be 0 if both of the squares are congruent to 0. –  anon Aug 26 '12 at 5:22
add comment

2 Answers

Suppose $a_1 = 3 q_1 + r_1$ and $b_1 = 3 q_2 + r_2$, where $r_1$ and $r_2$ is either $-1$, $0$ or $1$. Then $$ a_1^2 + b_1^2 = 3 \left( 3 q_1^2 + 3 q_2^2 + 2 q_1 r_1 + 2 q_2 r_2 \right) + r_1^2 + r_2^2 $$ For $a_1^2 + b_1^2$ to be divisible by $3$, we should have $r_1^2 + r_2^2 = 0$, since $0\leqslant r_1^2+r_2^2 < 3$. Enumerating 9 cases, only $r_1 = r_2 = 0$ assure the divisibility.

This is essentially the answer anon gave in his comment.

share|improve this answer
add comment

Well, we have two possibilities, first if neither $a_1$ nor $b_1$ is divisible by $3$ then that means that they have the form $a_1 = 3k \pm 1$ and $b_1 = 3t \pm 1$. Then $$a_1^2 + b_1^2 = (3k \pm 1)^2 + (3t \pm 1)^2 = 9k^2 \pm 6k + 1 + 9t^2 \pm 6t + 1 = 3A + 2$$

where $A = 3k^2 \pm 2k + 3t^2 \pm 2t$ and thus since $a_1^2 + b_1^2 = 3A + 2$ we can conclude that $3 \nmid a_1^2 + b_1^2$.

The other possibility is that exactly one of $a_1$ or $b_1$ is divisible by $3$. Let's assume that $a_1$ is divisible by $3$ but $b_1$ isn't. Then they have the form $a_1 = 3k$ and $b_1 = 3t \pm 1$. Thus

$$ a_1^2 + b_1^2 = (3k)^2 + (3t \pm 1)^2 = 9k^2 + 9t^2 \pm 6t + 1 = 3B + 1 $$

where $B = 3k^2 + 3t^2 \pm 2t$ so again since $a_1^2 + b_1^2 = 3B + 1$ then $3 \nmid a_1^2 + b_1^2$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.