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

 Abstract Algebra Abstract Algebra Math Forum

 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
 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:
 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?

 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 ill-suited to explain.
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.

 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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post ustus Abstract Algebra 4 October 14th, 2012 12:00 PM MastersMath12 Abstract Algebra 1 September 24th, 2012 11:07 PM ThatPinkSock Abstract Algebra 1 November 11th, 2011 04:25 AM Jamers328 Abstract Algebra 15 October 29th, 2008 12:21 PM micle Abstract Algebra 0 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top