# Prove no odd integer can be expressed as 4k+1 and 4j-1

• Aziza
I could be wrong though.In summary, the conversation discusses how to prove that there is no odd integer that can be expressed in the form 4j-1 and 4k+1 for integers j and k. Various formulations and simplifications of the statement are considered, with the conclusion that the statement can be logically simplified but not equivalent to another statement. The conversation also touches on the use of logical restrictions and the importance of being mathematically rigorous in such proofs.
Aziza
I am preparing for my Fall bridge to abstract math course and came across following problem:

"Prove that there is no odd integer that can be expressed in the form 4j-1 and 4k+1 for integers j and k."

If you let
P(x) = "x is odd"
Q(x) = ($\exists$j$\in$$Z$)(x=4j-1)
R(x) = ($\exists$k$\in$$Z$)(x=4k+1)

Then literally I understand the above statement as:
$\neg$[$\exists$x$\in$$Z$][ P(x)$\Rightarrow$( Q(x) $\wedge$ R(x) ) ]

But is this the same thing as:
[$\forall$x$\in$$Z$][ P(x)$\Rightarrow$( Q(x) $\vee$ R(x) ) ]
??

If you logically simplify both of these statements, they turn out to not be logically equivalent, but they both seem to equally fit the meaning of the initial statement. The latter just seems to have a simpler formal proof because it is equivalent to
[$\forall$x$\in$$Z$][ P(x)$\wedge\neg$Q(x)$\Rightarrow$R(x) ) ] , so in the proof you can just assume P(x)$\wedge\neg$Q(x) and use that to get to R(x)..

Aziza said:
Then literally I understand the above statement as:
$\neg$[$\exists$x$\in$$Z$][ P(x)$\Rightarrow$( Q(x) $\wedge$ R(x) ) ]

That is how I understood the statement.

But is this the same thing as:
[$\forall$x$\in$$Z$][ P(x)$\Rightarrow$( Q(x) $\vee$ R(x) ) ]
??

No, they are not the same thing. Can you explain why you think they are the same think??

Suppose not, suppose there IS some n where n=4k+1=4j-1
then it stands to reason that (4j-1)-(4k+1)=0
see what you can conclude from there :-)

Last edited:
micromass said:
That is how I understood the statement.

No, they are not the same thing. Can you explain why you think they are the same think??

I realized that in [∀x∈Z][ P(x)⇒( Q(x) ∨ R(x) ) ] , for the 'or' I meant the exclusive or, so I actually mean:
[∀x∈Z] { [ P(x)∧¬Q(x)]⇒R(x) ] ∧ [ P(x)∧Q(x)]⇒¬R(x) ] }
For the given P,Q and R this can easily be proven true.

So since P is true and P(x)⇒( Q(x) ∨ R(x) ) is true, then ( Q(x) ∨ R(x) ) must be true (again meaning exclusive or).

So we know that exactly one of Q or R is true and exactly one is false, so Q(x) ∧ R(x) must always be false, and so assuming P is true, ¬[∃x∈Z][ P(x)⇒( Q(x) ∧ R(x) ) ] is always true.

So since both statements are always true, they are equivalent...

Aziza said:
"Prove that there is no odd integer that can be expressed in the form 4j-1 and 4k+1 for integers j and k."

why make it so complicated?

i'm with tt2348's method …
tt2348 said:
Suppose not, suppose there IS some n where n=4k+1=4j-1
then it stands to reason that (4j-1) - (4k+1)=0
see what you can conclude from there :-)

tt2348 said:
Suppose not, suppose there IS some n where n=4k+1=4j-1
then it stands to reason that (4j-1)-(4k+1)=0
see what you can conclude from there :-)

Then 2(j-k)=1, so j-k must be 1/2, so j and k cannot both be integers as required :)
My question however was not how to prove, just how the statement to be proved could possibly be restated

tiny-tim said:
why make it so complicated?

i'm with tt2348's method …

haha idk my book likes complications i guess lol. but guys i know how to prove this, I am just more interested in how this statement can be equivalently restated and if i made any errors in my second post in trying to show that the literal logical translation of the initial statement is equivalent to my interpretation

Last edited:
tiny-tim said:
why make it so complicated?
Because they're pure math people?? Their notion of a good time appears to involve things like self-inflicted use of torture devices straight out of the Inquisition. To have a truly jolly good time they have to go well beyond crude Torquemada-like torture devices. Inverting universal and existential quantifiers, now that's a good time.

i'm with tt2348's method …
But that's not fun!

Using logical restrictions.. you can drop the P(x) requirement.
since regardless, even or odd, there is no integer such that x=4k-1=4j+1
so it boils down to x is an integer=>~(Q(x)&R(x))
=>(~q)v(~r)

or it's converse, Q(x)&R(X)=> x isn't an integer

tt2348 said:
Using logical restrictions.. you can drop the P(x) requirement.
since regardless, even or odd, there is no integer such that x=4k-1=4j+1
so it boils down to x is an integer=>~(Q(x)&R(x))
=>(~q)v(~r)

Right, but every odd integer is either R or Q, but not both and not neither, am i right? That's what I was trying to prove in my second post.

yes, it is indeed an exclusive or.
But you need to be careful with your formulation
F=>F
is true
also
F=>T
is true
Generally, logical propositions alone are not enough to be mathematically rigorous, and most professors want something using significantly less notation.

Aziza said:
Right, but every odd integer is either R or Q, but not both and not neither, am i right? That's what I was trying to prove in my second post.
That's certainly true, but wouldn't the original statement be true even if neither R nor Q were true? It seems like you're adding an additional condition by saying one of them has to be true.

## 1. Why is it impossible to express an odd integer as 4k+1 or 4j-1?

The proof for this statement relies on the properties of even and odd numbers. An odd integer can be represented as 2k+1, where k is any integer. When we substitute this expression into the given forms (4k+1 and 4j-1), we get 4k+1 = 2(2k)+1 and 4j-1 = 2(2j)-1. Both of these expressions result in an even number, which contradicts the fact that we started with an odd integer. Therefore, it is impossible to express an odd integer as 4k+1 or 4j-1.

## 2. Can you provide a specific example to illustrate this statement?

Yes, let's take the odd integer 9 as an example. If we try to express it as 4k+1, we get 4k+1 = 4(2)+1 = 9, which is correct. But if we try to express it as 4j-1, we get 4j-1 = 4(2)-1 = 7, which is incorrect. This shows that the given statement is true and an odd integer cannot be expressed as 4k+1 or 4j-1.

## 3. How does this statement relate to the properties of divisibility?

This statement is related to the property of divisibility by 4. Any number that is divisible by 4 can be expressed as 4k, where k is any integer. Similarly, any number that leaves a remainder of 1 when divided by 4 can be expressed as 4k+1 and any number that leaves a remainder of 3 when divided by 4 can be expressed as 4k-1. Since an odd integer will always leave a remainder of 1 when divided by 4, it cannot be expressed in the form of 4k+1 or 4j-1.

## 4. Does this statement hold true for all odd integers?

Yes, this statement holds true for all odd integers. The proof for this statement is based on the fundamental properties of even and odd numbers, which applies to all odd integers. Therefore, it is impossible to express any odd integer as 4k+1 or 4j-1.

## 5. Can this statement be extended to other forms such as 6k+1 and 6j-1?

Yes, this statement can be extended to other forms such as 6k+1 and 6j-1. The same logic and proof used for the given forms (4k+1 and 4j-1) can be applied to other forms as well. In fact, this statement can be extended to any form of 2nk+1 and 2nj-1, where n is any integer. This is because an odd integer can always be represented as 2k+1, where k is any integer.

• Calculus and Beyond Homework Help
Replies
15
Views
2K
• Math Proof Training and Practice
Replies
3
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
7
Views
2K
• Calculus and Beyond Homework Help
Replies
4
Views
1K
• Calculus and Beyond Homework Help
Replies
16
Views
1K
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
4
Views
2K
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
2
Views
2K