My Math Forum  

Go Back   My Math Forum > College Math Forum > Abstract Algebra

Abstract Algebra Abstract Algebra Math Forum


Reply
 
LinkBack Thread Tools Display Modes
May 31st, 2008, 01:47 PM   #1
Newbie
 
Joined: May 2008

Posts: 16
Thanks: 0

Abstract Algebra Proof - Form of a^2, a an integer

I'm going back through my Abstract Algebra text and trying to do all of the problems as preparation for graduate school. I'm using Hungerford's "Abstract Algebra: An Introduction." Unfortunately, silly me is stuck on a really early problem.

The exercise is to prove that for any integer a, a^2 takes the form 3k or 3k + 1, k an integer. The hint is to use the fact that the division algorithm gives that a must be of the form 3q, 3q + 1, or 3q + 2. THIS IS THE STEP I DON'T UNDERSTAND.

Using that hint, I can, of course, show that a^2 has the required form. What I don't understand is how that hint follows from the division algorithm. Without taking that statement on faith, I can't do the problem.

For reference, here's the statement of the division algorithm:
Let a, b be integers with b >0. Then there exist unique integers q, r such that a = bq + r and 0 <= r <b.

I feel like I must be missing something really obvious. Can anyone explain it to me?
karasuman is offline  
 
May 31st, 2008, 02:14 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
The division algorithm says that any integer n can be written in the form qD + r with 0 <= r < D for a given divisor D. For D = 3, r must be 0, 1, or 2.
CRGreathouse is offline  
May 31st, 2008, 02:25 PM   #3
Newbie
 
Joined: May 2008

Posts: 16
Thanks: 0

Quote:
Originally Posted by CRGreathouse
The division algorithm says that any integer n can be written in the form qD + r with 0 <= r < D for a given divisor D. For D = 3, r must be 0, 1, or 2.
Yes. How do we arrive at deciding that D = 3?
karasuman is offline  
May 31st, 2008, 02:58 PM   #4
Senior Member
 
Joined: May 2007

Posts: 402
Thanks: 0

Well, this is something your problem states.
milin is offline  
May 31st, 2008, 03:10 PM   #5
Newbie
 
Joined: May 2008

Posts: 16
Thanks: 0

The problem asks me to prove that a^2 = 3k or 3k + 1 for some integer k. How does that allow me to assume that a = 3q + r? I have to prove this for any a. Or...wait, is that the whole point? That any integer a is at most + 2 away from a multiple of 3?
karasuman is offline  
May 31st, 2008, 03:27 PM   #6
Senior Member
 
Joined: May 2007

Posts: 402
Thanks: 0

This is a basic induction! You always first denote that the thing you need to prove is true and then try do show a tautology using this! So, you say that it is true that a^2 = 3k or a^2 = 3k + 1 and then try to prove it.
milin is offline  
May 31st, 2008, 05:53 PM   #7
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
I had to read the post over three times to understand what the problem was. "Why does it say 'division algorithm'? Just consider the three residue classes modulo 3, ..." Maybe that means I'm ill-suited to explain.
CRGreathouse is offline  
June 1st, 2008, 04:33 AM   #8
Newbie
 
Joined: May 2008

Posts: 16
Thanks: 0

Quote:
Originally Posted by CRGreathouse
I had to read the post over three times to understand what the problem was. "Why does it say 'division algorithm'? Just consider the three residue classes modulo 3, ..." Maybe that means I'm ill-suited to explain.
No, I get what you're saying. I think it was the statement of the problem that threw me off so completely. If this had been in my number theory book instead of my abstract algebra book, I wouldn't have had a problem seeing how I needed to approach it... But it said to apply the division algorithm! What a pain.

I still don't get how this is simple induction, like a previous poster suggested. :-/ I see how to do it now... and that has nothing to do with induction.
karasuman is offline  
June 3rd, 2008, 08:23 AM   #9
Senior Member
 
Joined: Oct 2007
From: Chicago

Posts: 1,701
Thanks: 3

I would assume it said to apply the division algorithm either because not everyone has experience with residue classes, or because the division algorithm is somehow useful in algebra...

I don't know, but every abstract algebra text puts a ridiculous amount of emphasis on the division algorithm in the first chapter or two.
cknapp is offline  
August 13th, 2008, 02:01 PM   #10
Member
 
Joined: Aug 2008

Posts: 84
Thanks: 0

Re: Abstract Algebra Proof - Form of a^2, a an integer

I was perusing the topics, and though this old, it seems no one came up with a satisfying solution that fully utilized the [amazing] power of the division algorithm. So I thought I'd throw in my two cents.

let a be an integer, then by the DA there exists q, r in Z s.t. a = 3q+r, where r is, of course, less than 3 and greater than or equal to zero. So we have a a^2 = 9q^2+6qr + r^2. So if r = 0, we certainly have a^2 = 3k, and if r = 1, it follows that a^2 = 3k+1 as well. Not the somewhat trickier part. If r = 2 we have a^2 = 9q^2 +12q+4 = 9q^2 +12q+3 + 1 = 3(q^2 +4q) + 1. So even if r = 2, a^2 still has the form 3k+1. And we didn't have to resort to modular arithmetic!
Spartan Math is offline  
Reply

  My Math Forum > College Math Forum > Abstract Algebra

Tags
abstract, algebra, form, integer, proof



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Abstract Algebra Need Help ustus Abstract Algebra 4 October 14th, 2012 12:00 PM
Abstract Algebra Help MastersMath12 Abstract Algebra 1 September 24th, 2012 11:07 PM
Herstein: Abstract Algebra Proof (Sylow's Theorem) ThatPinkSock Abstract Algebra 1 November 11th, 2011 04:25 AM
Abstract Algebra - Proof involving groups Jamers328 Abstract Algebra 15 October 29th, 2008 12:21 PM
Abstract Algebra micle Abstract Algebra 0 December 31st, 1969 04:00 PM





Copyright © 2019 My Math Forum. All rights reserved.