
Abstract Algebra Abstract Algebra Math Forum 
 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? 
May 31st, 2008, 02:14 PM  #2 
Global Moderator 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.

May 31st, 2008, 02:25 PM  #3  
Newbie Joined: May 2008 Posts: 16 Thanks: 0  Quote:
 
May 31st, 2008, 02:58 PM  #4 
Senior Member Joined: May 2007 Posts: 402 Thanks: 0 
Well, this is something your problem states.

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?

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.

May 31st, 2008, 05:53 PM  #7 
Global Moderator 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 illsuited to explain.

June 1st, 2008, 04:33 AM  #8  
Newbie Joined: May 2008 Posts: 16 Thanks: 0  Quote:
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.  
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. 
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! 

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 