# Odd positive integer proof

1. Nov 20, 2005

### jmn_153

Can't figure it out

Prove that if n is an odd positive integer, then one of the numbers n+5 or n+7 is divisible by 4

My thoughts I dunno if this is right- Multiply n+5 and n+7, because if one of them is a multiple by 4 then shouldn't their product be divisible 4

2. Nov 20, 2005

### matt grime

2 times 2 is divisible by 4, neither of 2 or 2 is divisible by 4.

whenever you hear the phrase: suppose n is odd, then let n=2m+1 will probably help. It does here, though it is then a two line proof. you can do it in one line if you just think mod 4 from the start.

Last edited: Nov 20, 2005
3. Nov 20, 2005

### turbo

Add a series of positive odd integers to 5 and to 7 and jot down the results. Just add as if n=1,3,5,7 etc. You shouldn't get too far down the list before you notice a pattern, and can construct your proof.

4. Nov 20, 2005

### mathphys

Hi!

The problem can be easily solved using congruencies modulus 4. I will use the symbol '=' to denote 'congruent with'

First, n is and odd positive integer then n=1 (mod 2) and then one of the following holds

a) n=1 (mod 4)
b) n=3 (mod 4)

now we have that

5=1 (mod 4)
and 7=3 (mod 4)

if case a) holds then

(n+5)= 2 (mod 4)
(n+7)= 0 (mod 4)

if case b) holds then

(n+5)= 0 (mod 4)
(n+7)= 2 (mod 4)

Since a) and b) cannot be satisfied simulstaneously then just one of the numbers n+5 or n+7 is divisible by 4.

Note: what i mean with "congruencies", (mod 4) and the equations above?, This:

1=1 (mod 4), 2=2 (mod 4), 3=3 (mod 4), 4=0 (mod 4),
5=1 (mod 4), 6=2 (mod 4), ............. 8=0 (mod 4) and so on....

To the left of the '=' signs is the number in question, and to right the residue when it is divided by 4.

5. Nov 20, 2005

### jmn_153

oh ok, thanks for your help

What's mod???

6. Nov 20, 2005

### matt grime

7. Nov 20, 2005

### matt grime

remainder after division.

x= y mod n means x and y leave the same remainder upon division by n.

obviously any odd number must leave remainder 1 or 3 after division by 4. remainder 0 or 2 means that it is either a multiple of 4 or 2 more than a multiple of 4 and they're both even numbers (remember the definitions: something is even if it is 2k and odd if it is 2k+1)

8. Nov 20, 2005

### jmn_153

I get it now, thanks alot man

9. Nov 20, 2005

### mathphys

Sorry!

uh, i didn't know sorry matt, i was just trying to help. In fact i do not read your answer, just jmn problem. it will not happend again, just clues from now ;).

Hi Jmn, i think that if you are going to be solving problems of this kind (arithmetical ones) it would be nice if you can check the notion of modules and congruencies, and some theorems/properties related to them, they will save you a lot of time.

http://mathworld.wolfram.com/Modulus.html this link explains what is a modulus.

and this one explains congruencies
http://mathworld.wolfram.com/Congruence.html

Regards

P.S. By the way, i can write my "14 lines answer" in a line also, wait, in half a line.. ;) ..even..

Last edited: Nov 20, 2005
10. Nov 20, 2005

### matt grime

*modulo* or just plain *mod* arithmetic. modules are something else entirely and completely unrelated to the question (well, almost completely unrelated).

11. Nov 20, 2005

### mathphys

yep

yep, modulus, my typos ;)