# Positive integer proof

• Aug 2nd 2010, 07:45 AM
darknight
Positive integer proof
If $n$ is a natural number, then
$(2003 + \frac{1}{2})^n + (2004 + \frac{1}{2})^n$ is a positive integer:

A) when $n$ is even
B) when $n$ is odd
C) only when $n=117$ or $n=119$
D) only when $n=1$ or $n=3$

====================================

Simplifying the expression,
$(\frac{4007^n + 4009^n}{2^n})$
Therefore, $(4007^n + 4009^n)$ must be divisible by $(2^n)$
But how do I proceed from here? Can it be done without the binomial theorem?
• Aug 2nd 2010, 08:15 AM
undefined
Quote:

Originally Posted by darknight
If $n$ is a natural number, then
$(2003 + \frac{1}{2})^n + (2004 + \frac{1}{2})^n$ is a positive integer:

A) when $n$ is even
B) when $n$ is odd
C) only when $n=117$ or $n=119$
D) only when $n=1$ or $n=3$

====================================

Simplifying the expression,
$(\frac{4007^n + 4009^n}{2^n})$
Therefore, $(4007^n + 4009^n)$ must be divisible by $(2^n)$
But how do I proceed from here? Can it be done without the binomial theorem?

This might not be the best solution, but we can use the multiple choice nature to our advantage.

n = 1 is easily verified true, which rules out A and C. In order to test between B and D, all we need is to check n = 5.

We want to know what is $(4007^5 + 4009^5)$ modulo 2^5. So, reduce to $(7^5 + 9^5)$ which turns out to be congruent to 16 mod 32. (On paper we can do 7 * 49 * 49 + 9 * 81 * 81 which becomes 7 * 17 * 17 + 9 * 17 * 17 which is just 16 * 17 * 17 which is clearly divisible by 16 but not 32.) So the answer is D.
• Aug 2nd 2010, 04:32 PM
Could you explain how you simplified the expression? I'm a bit rusty, but I tried the binomial theorem, and 'simplified' the equation to get

$\sum\binom{n} {k}[(2003)^{n-k} + (2004)^{n-k}](1/2)^k$
with k = 0 to n.

how the question sets up the answers, the next step might be to seperate this sum into two sums, one with odd k terms and the other with even k terms.

again, I'm rusty. blame summer haha.
• Aug 2nd 2010, 04:53 PM
undefined
Quote:

Could you explain how you simplified the expression? I'm a bit rusty, but I tried the binomial theorem, and 'simplified' the equation to get

$\sum\binom{n} {k}[(2003)^{n-k} + (2004)^{n-k}](1/2)^k$
with k = 0 to n.

how the question sets up the answers, the next step might be to seperate this sum into two sums, one with odd k terms and the other with even k terms.

again, I'm rusty. blame summer haha.

Actually the binomial theorem was not used for that simplification; write 2003 + 1/2 as 4007/2, likewise with 2004 + 1/2, then distribute the exponent to numerators and denominators, then the two terms have a common denominator of 2^n
• Aug 2nd 2010, 04:59 PM
eumyang
Quote:

Originally Posted by darknight
If $n$ is a natural number, then
$(2003 + \frac{1}{2})^n + (2004 + \frac{1}{2})^n$ is a positive integer:

A) when $n$ is even
B) when $n$ is odd
C) only when $n=117$ or $n=119$
D) only when $n=1$ or $n=3$

====================================

Simplifying the expression,
$(\frac{4007^n + 4009^n}{2^n})$
Therefore, $(4007^n + 4009^n)$ must be divisible by $(2^n)$
But how do I proceed from here? Can it be done without the binomial theorem?

Note that:
$4007^1$ ends with a 7,
$4007^2$ ends with a 9,
$4007^3$ ends with a 3,
$4007^4$ ends with a 1,
$4007^5$ ends with a 7,
etc., etc.

... and:
$4009^1$ ends with a 9,
$4009^2$ ends with a 1,
$4009^3$ ends with a 9,
etc., etc.

EDIT: Oops, a little late there... :)
• Aug 2nd 2010, 09:15 PM
darknight
Thanks guys!