Number Theory

Printable View

July 15th 2008, 06:14 PM
JCIR

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)
July 15th 2008, 06:25 PM
Jhevon

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 $a^2 \equiv 1~ \text{mod}8$ means $8 \mid (a^2 - 1)$ . thus, it suffices to show that $a^2 - 1$ is a multple of 8 if $a$ is odd.

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

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

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

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

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

Thus, we have the desired result if $\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
July 15th 2008, 06:49 PM
PaulRS

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 $ x^2 + y^2 \equiv 3\left( {\bmod 4} \right) $ with $ x,y \in \mathbb{N} $ is impossible because, for any natural number n we have either $ n^2 \equiv 0\left( {\bmod 4} \right) $ or $ n^2 \equiv 1\left( {\bmod 4} \right) $ , and since $ x^2 + y^2 \equiv 3\left( {\bmod 4} \right) $ is impossible it follows that b) must be true
July 15th 2008, 06:55 PM
Jhevon

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 $n$ be as stated.

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

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

case 1: both $a,b$ are even

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

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

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

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

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

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

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

we can also use the by cases method to prove/disprove the converse
July 15th 2008, 08:44 PM
Isomorphism

Quote:

Originally Posted by Jhevon

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

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

$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 $8|a^2 - 1$ is sufficient.
July 15th 2008, 09:05 PM
Jhevon

Quote:

Originally Posted by Isomorphism

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

$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 $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
July 15th 2008, 09:11 PM
Isomorphism

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.
July 16th 2008, 05:59 PM
Catherine Morland

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.

$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. $\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. $12\equiv0\pmod{4}$ , $21\equiv1\pmod{4}$ and $6\equiv2\pmod{4}$ all can’t be written as a sum of two integer squares.
July 18th 2008, 04:33 PM
JaneBennet

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

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

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