Thread: elem. numbr theory - prove P

1. elem. numbr theory - prove P

OK: prove "If n is an odd integer, then there exists an integer x such that n = 4x + 1 or n = 4x + 3.

I could also prove its negation, which is: For some integer x such that n is odd and for all integer x, n doesn't equal 4x + 1 and n doesn't equal 4x + 3.

So I start off with: Let n = 2k + 1 for some integer k.
Then I'm stuck ... lol

(I wanna prove the first, because I feel as though it would be easier) - but how do I show 2k + 1 = 4x + 1 or 4x + 3???

2. Hello,

For that, I would do a direct proof o.O

If n is odd, okay, it is odd.

Now, a number can be written in 4 ways :
4x
4x+1
4x+2
4x+3

Which of those are indeed odd ??
You're thus proving that if n is odd, then there's only ... ways it can be written.

3. To expand on it, you basically have to prove that 4x + 1 and 4x + 3 are, in fact odd.

For the first option: 4x

If k = 2x, then:

4x = 2k, which is even.

For the second option: 4x + 1

If k = 2x, then:

4x + 1 = 2k + 1, which is odd

For the third option: 4x + 2

First:

4x + 2 = 2(2x + 1)

Now, if k = 2x + 1, then

4x + 2 = 2k, which is even

For the last option: 4x + 3

First:

4x + 3 = (4x + 2) + 1 = (2(2x + 1)) + 1

If k = 2x + 1, then

4x + 3 = 2k + 1

And you can easily see that only 4x + 1 and 4x + 3 are odd.

4. ok, but why would you have to bring in 4x and 4x + 2 - the problem doesn't mention those and they're obviously going to be even. so why even bring them in?

so I tried working it:
Let n = 2k + 1 for some integer k.
So 2k + 1 = 4x + 3
2k = 4x + 2
2k = 2(2x + 1)
k = 2x + 1

thus they're the same ... ???

5. Originally Posted by cassiopeia1289
huh? you lost me:

so I tried working it:
Let n = 2k + 1 for some integer k.
So 2k + 1 = 4x + 3
2k = 4x + 2
2k = 2(2x + 1)
k = 2x + 1

thus they're the same ... ???
If you're going to do it that way, you have to do something different:

Let n = 2k + 1 for some integer k.
So n = 4x + 3 for some integer x
n = (4x + 2) + 1
n = 2(2x + 1) + 1
Now, if you let k = 2x + 1, then
n = 2k + 1
Thus for some integer x, 4x + 3 yields an odd integer n.

6. ok, I get it.
so how would you conclude it: therefore, the odd integer n does equal 4x+3.

it just looks really disorganized and a bit confusing, but I'm pretty sure I understand it.

7. What you do is:

1. State the assertion and any other information:

If n is an odd integer, then there exists an integer x such that n = 4x + 1 or n = 4x + 3.

n is odd, therefore n = 2k + 1

2. Separate this into cases:

Case 1: There exists an integer x such that n = 4x + 1

Case 2: There exists an integer x such that n = 4x + 3

3. Prove each case directly:

Case 1:

If n is odd, then n = 2k + 1.

To prove this, we have to show that n = 4x + 1 is also an odd integer. We want to go from n = 4x + 1 to n = 2k + 1, then we have proved that there is at least one (more than likely all) x that causes n to be odd.

n = 4x + 1

Now, we have to turn it into 2k + 1:

n = 4x + 1

We know that 4x = 2(2x), so if we set k = 2x, we get:

n = 2k + 1

Therefore, there is at least one x that causes n to be an odd integer for n = 4x + 1.

Case 2:

n = 4x + 3

We know that 4x + 3 = (4x + 2) + 1 and that 4x + 2 = 2(2x + 1), so that:

n = 2(2x + 1) + 1

If we set k = (2x + 1), we get:

n = 2k + 1.

The two x's we get specifically are $x = \frac{1}{2}k, \ \frac{k-1}{2}$

The first x is for the form 4x + 1 and the second x is for the form 4x + 3.

Therefore, there exists an integer x such that n is either 4x + 1 or 4x + 3.