# euclid's division lemma for real numbers

use euclid's division lemma to show that the square of any positive integer is either of the form 3m or 3m+1 for some integer m.

### Comments for euclid's division lemma for real numbers

 Mar 27, 2011 Euclid’s Division Lemma by: Staff The question: use euclid's division lemma to show that the square of any positive integer is either of the form 3m or 3m+1 for some integer m. The answer: When any positive integer is divided by 3, the results are always another integer “h” plus a remainder. The REMAINDER of dividing a positive integer divided by 3 is ALWAYS: 0, 1, or 2 In other words, every integer is of the form: h + 0, or h + 1, or h + 2 Try it: 1 ÷ 3 = 0 (the “h” = 0) plus a remainder of 1 2 ÷ 3 = 0 (the “h” = 0) plus a remainder of 2 3 ÷ 3 = 1 (the “h” = 1) plus a remainder of 0 4 ÷ 3 = 1 (the “h” = 1) plus a remainder of 1 5 ÷ 3 = 1 (the “h” = 1) plus a remainder of 2 6 ÷ 3 = 2 (the “h” = 2) plus a remainder of 0 . . . In other words, every POSITIVE INTEGER only has one of THREE forms: h + 0 h + 1 h + 2 Since “h” is the result of dividing by 3, then “h” can be rewritten as 3 times another integer “k”, as follows: h + 0 = 3k+0 h + 1 = 3k+1 h + 2 = 3k+2 “m” = another integer. Squaring each of the three forms an integer can take (3k+0, 3k+1, and 3k+2), the results are: (3k + 0)² = 9k² = 3*3k² = 3*(another integer) = 3m (3k + 1)² = 9k² + 6k + 1 = 3*k(3k + 2) + 1 = 3*(another integer) + 1 = 3m + 1 (3k + 2)² = 9k² + 12k + 4 = 3*(3k² + 4k) + 1 = 3*(another integer) + 1 = 3m + 1 Notice that while a positive integer can have three forms (h + 0, h + 1, or h + 2), the SQUARE of a positive integer has ONLY TWO POSSIBLE FORMS (3m and 3m + 1). In conclusion, the square of a positive integer can only have two forms: 3m, or 3m + 1 Thanks for writing. Staff www.solving-math-problems.com