Odd Integer Divisibility Proof: n+5 or n+7 divisible by 4?

[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 don't know 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

 

[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.

 

[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.

 

[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.

 

[jmn_153]

oh ok, thanks for your help

What's mod?

 

[matt grime]

we're supposed to not just give people the answers, mathsphys. your 14 line answer was in fact my one line answer.

 

[matt grime]

oh ok, thanks for your help
What's mod?

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)

 

[jmn_153]

I get it now, thanks a lot man

 

[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 happened 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..

 

[matt grime]

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

 

[mathphys]

yep

yep, modulus, my typos ;)