Number Theory

Part a) Let a be an odd integer. Prove that a^2 is congruent to 1 mod 8. Deduce that a^2 is congruent to 1mod4.

Part b) Prove that if n is a positive integer such that n is congruent to 3mod4, then n cannot be written as the sum of two squares of integers.

Prove or disprove the converse of part b)

Quote:

---

Originally Posted by JCIR

Part a) Let a be an odd integer. Prove that a^2 is congruent to 1 mod 8. Deduce that a^2 is congruent to 1mod4.

---

recall that $\displaystyle a^2 \equiv 1~ \text{mod}8$ means $\displaystyle 8 \mid (a^2 - 1)$. thus, it suffices to show that $\displaystyle a^2 - 1$ is a multple of 8 if $\displaystyle a$ is odd.

Assume $\displaystyle a$ is odd. then we can write $\displaystyle a = 2n + 1$ for $\displaystyle n \in \mathbb{Z}$.

Thus, $\displaystyle a^2 - 1 = (a + 1)(a - 1)$

$\displaystyle = (2n + 2) \cdot 2n$

$\displaystyle = 4n^2 + 4n$ .......incidentally, we can easily show $\displaystyle a^2 \equiv 1 ~\text{mod}4$ from this

$\displaystyle = 8 \bigg( \frac {n^2 + n}2 \bigg)$

Thus, we have the desired result if $\displaystyle \frac {n^2 + n}2$ is an integer. i leave it to you to prove this. Hint: factorize the numerator, see what you can think of

Quote:

---

Originally Posted by JCIR

Part a) Let a be an odd integer. Prove that a^2 is congruent to 1 mod 8. Deduce that a^2 is congruent to 1mod4.
Part b) Prove that if n is a positive integer such that n is congruent to 3mod4, then n cannot be written as the sum of two squares of integers.
Prove or disprove the converse of part b)

---

Check that $\displaystyle
x^2 + y^2 \equiv 3\left( {\bmod 4} \right)
$ with $\displaystyle
x,y \in \mathbb{N}
$ is impossible because, for any natural number n we have either $\displaystyle
n^2 \equiv 0\left( {\bmod 4} \right)
$ or $\displaystyle
n^2 \equiv 1\left( {\bmod 4} \right)
$, and since$\displaystyle
x^2 + y^2 \equiv 3\left( {\bmod 4} \right)
$ is impossible it follows that b) must be true

Quote:

---

Originally Posted by JCIR

Part b) Prove that if n is a positive integer such that n is congruent to 3mod4, then n cannot be written as the sum of two squares of integers.

---

an alternative to Paul's solution (not as elegant)

we can do this by cases:

Let $\displaystyle n$ be as stated.

Since $\displaystyle n \equiv 3~\text{mod }4$, $\displaystyle n = 4k + 3$ for $\displaystyle k \in \mathbb{Z}$

Now, let $\displaystyle a,b \in \mathbb{Z}$


case 1: both $\displaystyle a,b$ are even

so, $\displaystyle a = 2n$ and $\displaystyle b = 2m$ for $\displaystyle m,n \in \mathbb{Z}$

thus, $\displaystyle a^2 + b^2 = 4n^2 + 4m^2$, which is even, and so cannot be equal to $\displaystyle 4k + 3$, which is odd.


case 2: both $\displaystyle a,b$ are odd.

take $\displaystyle a = 2n + 1$ and $\displaystyle b = 2m + 1$. then again, $\displaystyle a^2 + b^2$ is even


case 3: (without loss of generality) $\displaystyle a$ is odd, and $\displaystyle b$ is even.

taking $\displaystyle a = 2n + 1$ and $\displaystyle b = 2m$, we find that $\displaystyle a^2 + b^2 = 4(n^2 + m^2 + n) + 1 \ne 4k + 3$ for any $\displaystyle n,m,k \in \mathbb{Z}$, since we would have $\displaystyle a^2 + b^2 \equiv 1~\text{mod }4$.

thus, $\displaystyle n$ cannot be the sum of two squared integers



we can also use the by cases method to prove/disprove the converse

Quote:

---

Originally Posted by Jhevon

recall that $\displaystyle a^2 \equiv 1~ \text{mod}8$ means $\displaystyle 8 \mid (a^2 - 1)$. thus, it suffices to show that $\displaystyle a^2 - 1$ is a multple of 8 if $\displaystyle a$ is odd.

---

Maybe I am missing something obvious (Doh), but isnt the following true?

$\displaystyle 8|a^2 - 1, 4|8 \Rightarrow 4|a^2 - 1 \Rightarrow a^2 = 1 \mod 4$

Additionally I think a is odd is unnecessary, since $\displaystyle 8|a^2 - 1$ is sufficient.

Quote:

---

Originally Posted by Isomorphism

Maybe I am missing something obvious (Doh), but isnt the following true?

$\displaystyle 8|a^2 - 1, 4|8 \Rightarrow 4|a^2 - 1 \Rightarrow a^2 = 1 \mod 4$

---

yes, that's true. that would be for the "Deduce..." part of the problem, i never dealt with that really

Quote:

---

Additionally I think a is odd is unnecessary, since $\displaystyle 8|a^2 - 1$ is sufficient.

---

it doesn't work when a is even, since a^2 - 1 would be odd in that case and hence is not divisible by 8

Quote:

---

Originally Posted by Jhevon

yes, that's true. that would be for the "Deduce..." part of the problem, i never dealt with that really

it doesn't work when a is even, since a^2 - 1 would be odd in that case and hence is not divisible by 8

---

Whoops... I am sorry... I didnt see "Prove a^2 = 1 mod 8...". I thought it said assume a^2 = 1 mod 8.

Quote:

---

Originally Posted by JCIR

Part a) Let a be an odd integer. Prove that a^2 is congruent to 1 mod 8. Deduce that a^2 is congruent to 1mod4.

---

$\displaystyle a = 2k+1\ \implies\ a^2=4k(k+1)+1\equiv1\pmod{4}$

Note also that one of k and k+1 is even (since they are consecutive integers); hence 4k(k+1) is always divisible by 8. $\displaystyle \therefore\ a^2=4k(k+1)+1\equiv1\pmod{8}$.

Quote:

---

Part b) Prove that if n is a positive integer such that n is congruent to 3mod4, then n cannot be written as the sum of two squares of integers.

Prove or disprove the converse of part b)

---

The converse is false. $\displaystyle 12\equiv0\pmod{4}$, $\displaystyle 21\equiv1\pmod{4}$ and $\displaystyle 6\equiv2\pmod{4}$ all can’t be written as a sum of two integer squares.

Here’s a quick way of doing the first part.

If $\displaystyle a$ is odd, write $\displaystyle a=4n\pm1$.

Then $\displaystyle a^2=16n^2\pm8n+1=8n(2n\pm1)+1\equiv1\pmod{8}$