Prove For all integers a, 9 does not divide a^2 +3

[ryou00730]

Homework Statement

Trying to prove that for all integers a, 9 does not divide a^2 +3

Homework Equations

there exists no k such that a^2+3 = 9k

The Attempt at a Solution

Tried assuming not the case, so assumed a is an integer and 9 does not divide a^2 +3 to try to prove a contradiction showing that a can't be an integer in this case, but it went no where.

 

[micromass]

Have you tried induction?

 

[Dick]

I would look at the possible values of a^2 mod 9.

 

[ryou00730]

i don't know how i would use induction in this case to prove something is not divisible? and I don't know how to use the mod function either.

 

[cloud360]

if 9 divides a^2 +3

then you can write a^2+3 as...a^2+3=9q

if 9 DOES NOT divide a^2 +3

then you can write a^2+3 as...a^2+3=9q + 1 (or a^2+3 DOES NOT = 9q)

PROVE BY Induction


Step 1


Create given goal table to to picture all the info

Given =
1.a is in the set of Reals
2.a^2+3=9q +1 (or a^2+3 DOES NOT = 9q)

Goal=
(a+1)^2+3=9p + 1 (or a^2+3 DOES NOT = 9p)


(THEIR IS NO REASON TO ASSUME both equations will have a q)
Step 2
Prove for base case, where a=1

we get 1^2+3=9q

4 = 9q

since 4 can not be expressed in terms of 9q, it is not divisible by 9, so base case is true
Step 3
Start at goal

Assume (a+1)^2+3=9p+1

If we expand = a^2 + 2a +1 +3
Step 4 (method 1)
If this is divisible by 3, then a^2 + 2a +4= 9p +1...so

p= (a^2 + 2a +4)-1/9...where p is an integer


if we sub, let's say a=0, we get 3/9...this is not an integer, therefore it is not true for all integers as the propsition claimed "it is true for all integers", we have proved this proposition is false! (when we say it is true for all integers, then it must be true for k+1, or q+1 or p+1, or WHATEVER U WANNA CALL IT)

Step 4 (method 2)
write, a^2 + 2a +1 +3= 9p +1 , in the form:
a^2 + 2a +1 +3 = 9p +1....(1)

NOW, we were given an equation which stated a^2+3 = 9q +1 (i don't like using K's so i changed you original equation to a q)

if we sub this into (1), we get: 9q +2a +1 = 9p +1

9q +2a +1 cannot be factorised such that 9 stays outside e.g 9(blah...blah.blah). Therefore is not divisible by 9

if we factorise so that 9q +1 is outside, we have 9q +1 (1

 

[PAllen]

No need for induction, only simple logic. 9 divides numbers of form 9k, k a natural number. Equate this to a^2+3, solve for a^2. Arrange the side with 9 some different ways that might tell you it can't be a perfect square. What properties does a perfect square have in terms of its prime factors (how many of each prime factor must be present)? Really trivial algebre and almost trivial reasoning gives you the answer.

 

[PAllen]

3(3k-1) =? a^2

Can 3k-1 have 3 as a factor? QED

 

[Dick]

i don't know how i would use induction in this case to prove something is not divisible? and I don't know how to use the mod function either.

That's not good. There's a really simple proof using remainders mod 9. I think you ought to figure out what mod means.

 

[PAllen]

That's not good. There's a really simple proof using remainders mod 9. I think you ought to figure out what mod means.

Agree, but I don't see it as any simpler than the way I suggested. So the poster can choose from two simple methods.

 

[Dick]

Agree, but I don't see it as any simpler than the way I suggested. So the poster can choose from two simple methods.

Yep, poster has two methods to choose from. I like the quadratic residues thing, but that's just me.