Proof by logic

  • Thread starter Dr-NiKoN
  • Start date
  • #1
94
0
I'm supposed to prove that if:
n^2 % 3 = 0
Then
n % 3 = 0

I'm not sure how to proceed here?

Does it got something to do with setting n^2 to x?
x % 3 = 0
and
\frac{x}{n} % 3 = 0

Not sure how that helps..

The actual problem is to prove that if n^2 / 3 is a whole number, then n/3 is also a whole number. But, I can't figure out any other way to present it.
 
Last edited:

Answers and Replies

  • #2
NateTG
Science Advisor
Homework Helper
2,450
6
The actual problem is to prove that if n^2 / 3 is a whole number, then n/3 is also a whole number. But, I can't figure out any other way to present it.
Seems like that was good enough...

Assuming that [itex]n[/itex] is a whole number, we can apply the fundemental theorem of algebra, so [itex]n[/itex] has a unique prime factorization:
[tex]n=p_1^{a_1}\times p_2^{a_2}...[/tex]
Where all the [itex]p_i[/itex] are primes, and all the [itex]a_i[/itex] are whole numbers. Then [itex]n^2[/itex] has the following prime factorization:
[tex]n^2=p_1^{2a_1} \times p_2^{2a_2}...[/tex]

Should be pretty easy from there...
 
  • #3
HallsofIvy
Science Advisor
Homework Helper
41,847
967
Work from the other side. If n is not a multiple of 3 (i.e. if n/3 is not a whole number), then n must be of the form n= 3m+1 or n= 3m+2 for some whole number m.

Now square them: n2= (3m+1)2= 9m2+ 6m+ 1=
3(3m2+ 2m)+ 1. In other words, it is a multiple of 3 plus 1, not a multiple of 3.

if n= 3m+2, then n2= (3m+2)2= 9m2+ 12m+ 4=
3(3m2+ 4m+ 1)+ 1. Again, it is not a multiple of 3.

Okay, if n is not a multiple of 3, then n2 cannot be. What does that tell you about the case if n2 is a multiple of 3?
 
  • #4
matt grime
Science Advisor
Homework Helper
9,420
4
Or use the alternative characterizations of the primes:

p divides ab iff p divides either a or b.

Let =3, a=b=n
 
  • #5
94
0
I can't use prime factorization, since that is in a later chapter.

Work from the other side. If n is not a multiple of 3 (i.e. if n/3 is not a whole number), then n must be of the form n= 3m+1 or n= 3m+2 for some whole number m.
Doesn't this give me:
p = n^2 is even
q = n is even
(in logic, don't know the latex for it)
if NOT q then NOT p

How does this prove:
if q then p

I tried working with the implication law, but can't seem to figure out how you get there. Or is this just some common law of logic?
 
  • #6
59
0
Dr-NiKoN said:
Doesn't this give me:
p = n^2 is even
q = n is even
(in logic, don't know the latex for it)
if NOT q then NOT p
HallsOfIvy's method gives you:
p = n^2 is divisible by 3
q = n is divisible by 3
if NOT q then NOT p

Dr-NiKoN said:
How does this prove:
if q then p

It doesn't, but it proves if p then q... Which is what you originally wanted, no?
 
  • #7
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
You could exhaust over the possibilities for n % 3.
 
  • #8
HallsofIvy
Science Advisor
Homework Helper
41,847
967
"Doesn't this give me:
p = n^2 is even
q = n is even"

Well, no- the "negation" of "n is a multiple of 3" is not "n is even"!

It is a "law of logic" that "if p then q" is equivalent to "if not q then not p". That's called the contrapositive and is a special case of "proof by contradiction".
 
  • #9
94
0
Thanks guys,

this actually helped me to solve a couple of other problems(proving the contrapositive that is). :)
 

Related Threads on Proof by logic

  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
7
Views
9K
  • Last Post
Replies
6
Views
10K
Replies
6
Views
865
Replies
1
Views
2K
Replies
4
Views
1K
Replies
8
Views
2K
  • Last Post
Replies
17
Views
3K
Top