# MAT385-Proof by contraposition

• fritzh
In summary: If x is divisible by n, then there is an integer k such that x=kn. Then xy=(kn)y=(ky)n, and so xy is a multiple of n and is thus divisible by n....but note that the variable name has changed and that the only reason I bothered to change it is that I'm trying to be pedantic and that I'm a math teacher. In pretty much any other context, I'd just say "Similarly, if y is divisible by n, then xy is also divisible by n."
fritzh

## Homework Statement

28. Prove the given statement:
If the product of two integers is not divisible by an integer n, then neither integer is divisible by n.

## Homework Equations

Proof by contraposition

## The Attempt at a Solution

Originally the problem states:
(xy/n)'→(x/n /\ y/n)'
This seems like a handy time for contraposition because it makes more intuitive sense that:
(x/n /\ y/n) $\rightarrow$ (xy/n^2)

To which I think
a=((k)(k+1))/n^2
Where it gets hazy is where to go from here. If I wanted to do proof by induction then I would need some guidance on what to aim for. Would it be:
(k+1)(k+2)/(n^2)=a
?

#### Attachments

• logic.PNG
9.7 KB · Views: 725
fritzh said:

## Homework Statement

28. Prove the given statement:
If the product of two integers is not divisible by an integer n, then neither integer is divisible by n.

## Homework Equations

Proof by contraposition

## The Attempt at a Solution

Originally the problem states:
(xy/n)'→(x/n /\ y/n)'
This seems like a handy time for contraposition because it makes more intuitive sense that:
(x/n /\ y/n) $\rightarrow$ (xy/n^2)

To which I think
a=((k)(k+1))/n^2
Where it gets hazy is where to go from here. If I wanted to do proof by induction then I would need some guidance on what to aim for. Would it be:
(k+1)(k+2)/(n^2)=a
?

Assuming ##p'## is meant to denote the negation of ##p## and ##x/n## denotes "##x## is divisible by ##n##" (which is almost universally denoted ##n|x## in my experience), the form of the original claim is ##(xy/n)'\rightarrow[(x/n)'\land( y/n)']##, not what you have written. Or equivalently, by DeMorgan, ##(xy/n)'\rightarrow(x/n\lor y/n)'##.

The contrapositive, which I agree is much easier to prove, would be ##(x/n\lor y/n)\rightarrow (xy/n)##. You don't need anything fancy (like induction) to prove this. Just write down the definition of ##x/n## and follow your nose.

I see. Seeing the implication differently does change quite a bit. Thank you.

Is this sufficient?

Is the attached sufficient. By write the definition of x, did you mean x=kn?

#### Attachments

• 28logic.PNG
11.2 KB · Views: 460
fritzh said:
Is the attached sufficient.

Not as a proof of the given statement. Some of it looks like good scratch work that might lead to a proof and perhaps get incorporated into that proof. Other parts of it (like whatever is going on off to the side with ##k^2n^2=k^2n## and the fact that you have essentially stated that ##x=y## when that isn't necessarily true and the fact that you have assumed that both ##x/n## and ##y/n## when that isn't necessarily true) need to be discarded.

Also, don't be afraid to use words in your proof. A good proof really should read like what we would consider "standard" prose written in English (or whatever language you speak) with mathematical notation used to make the proof more readable. Look at the statement that you're proving; the only mathematical notation used is the letter ##n## so that the second half of the statement could refer to that integer by name.

By write the definition of x, did you mean x=kn?

Alright. So you're reading and writing mathematical proofs, which means you need to read carefully and also choose your words carefully.

I said
write down the definition of ##x/n##
not
write the definition of x
I'm not even sure what "the definition of x" would even mean in this problem.

Now, ##x=kn## is part of the definition of ##x/n##, but there's more. the full definition should look something like

##x/n## if and only if there is an integer ##k## such that ##x=kn##.

I know it might seem like I'm being a stickler, but all of the definition is important, not just the equation.

When you start off by writing "If ##x/n##, then there is an integer ##k## such that ##x=kn##," and you're trying to prove something about ##xy##, what's the next thing you might say? Oh, hey, "then ##xy=kny##." And if what you're trying to say about ##xy## is that it is also divisible by ##n## ...

Maybe

Let x be divisible by n:
x=kn
y=y
x*y=kn*y
xy is a multiple of n, so xy is divisible by n.
Proof by contraposition.

This is my first introduction to formal logic and proofs (MAT385) aside from proofs like those found in calc III. Thus, I thank you for the pointers on specifics.

It looks like you have the basic gist of the argument, though I'd point out that you haven't actually proven the contrapositive of the original claim.

Here's how I might write it up, just as a guide.

Claim: If xy is not divisible by n, then neither x nor y is divisible by n. (*)

Proof: We will prove the contrapositive, and so we must show that if either x or y is divisible by n, then xy is also divisible by n. (**)

If x is divisible by n, then there is an integer k such that x=kn. Then xy=(kn)y=(ky)n, and so xy is a multiple of n and is thus divisible by n. Similarly (***), if y is divisible by n, then xy is also divisible by n. Therefore if either x or y is divisible by n, then xy is also divisible by n.

And so by contraposition, the original claim is proven.##\Box##

(*) There isn't a math teacher/grader on the planet who won't love you for writing out the problem statement/claim before the solution. Do it. Seriously, do it. Be careful with paraphrasing the assigned problem, but do it.

(**) I've always been advised to let the proof reader know ahead of time what sort of proof they're about read in most instances that aren't straightforward, direct proofs. When you jump right in with "let x be divisible by n", the reader's fist though is "Why?! That's not one of the assumptions, and is actually the OPPOSITE of what you're trying to prove!" And then they read further and go "Oh, ok. I get it now." But for a second, they were confused and annoyed. You don't want the grader to be confused and annoyed by something you wrote, not even for a moment. It can also serve as a reference for YOU for what you need to get done in the proof; i.e. this is what I said I was going to do, and I'm not done until I do it.

(***) The proof of this sentence is almost the same as the previous proof; we're just switching around the roles of some of the letters. Be very careful with using "similarly" (or "trivial" or "obvious"). When in doubt, write it out.

My advisor always says, with regards to homework-style proofs, (1) tell me what you're going to do (i.e. the claim) (2) tell me how you're going to do it (3) do it (4) let me know when you're done, and, if it's not too much trouble, remind me what you did.

Also, I would encourage you to read out loud what you have written. Or rewrite what you have written without using mathematical notation. If it sounds silly, you may want to jazz it up a bit (just a bit) with some exposition. A few "so"s and "then"s and "therefore"s go a long way.

Finally, read a lot of proofs. And watch your professor(s) do proofs. Listen to what they say as much (if not more) than you read what they write. Most of the proof is coming out of their mouth, and probably doesn't end up on the blackboard. I learned a lot about the proof-writing process just by seeing other people's proofs.

fritzh said:

## Homework Statement

28. Prove the given statement:
If the product of two integers is not divisible by an integer n, then neither integer is divisible by n.

## Homework Equations

Proof by contraposition

## The Attempt at a Solution

Originally the problem states:
(xy/n)'→(x/n /\ y/n)'
This seems like a handy time for contraposition because it makes more intuitive sense that:
(x/n /\ y/n) $\rightarrow$ (xy/n^2)

To which I think
a=((k)(k+1))/n^2
Where it gets hazy is where to go from here. If I wanted to do proof by induction then I would need some guidance on what to aim for. Would it be:
(k+1)(k+2)/(n^2)=a
?

You're making this way too complicated!

The first thing to do is write down the contraposition in plain English. Then, you should be almost there! To help you a bit, I've put some variables in:

"If x = yz is the product of two integers and x is not divisible by an integer n, then neither integer y nor z is divisible by n."

Try to write down the contraposition of that statement.

Cool. Thanks for all the help. I'm a chemistry major who keeps taking math classes for some reason.

## 1. What is "Proof by contraposition"?

Proof by contraposition is a method of proving a statement by showing its logical equivalent inverse statement. It states that if "If A implies B" is true, then "if not B, then not A" is also true. This is also known as the "proof by contradiction" method.

## 2. When is "Proof by contraposition" used?

Proof by contraposition is used when attempting to prove a statement that is difficult to prove directly. It is also used when attempting to prove a statement using the "proof by contradiction" method.

## 3. What are the steps for "Proof by contraposition"?

The steps for proof by contraposition are as follows:

1. Assume the negation of the statement you want to prove.
3. Therefore, the original statement must be true.

## 4. What is the difference between "Proof by contraposition" and "Proof by contradiction"?

The main difference between proof by contraposition and proof by contradiction is that proof by contraposition deals with the logical equivalence of the inverse statement, while proof by contradiction deals with the logical contradiction of the negation of the original statement.

## 5. Can "Proof by contraposition" be used in all mathematical proofs?

Yes, proof by contraposition can be used in all mathematical proofs as it is a valid proof technique. However, it may not always be the most efficient method for a particular proof. It is important for a mathematician to be familiar with a variety of proof techniques and use the one that is most appropriate for a particular proof.

• Calculus and Beyond Homework Help
Replies
15
Views
2K
• Calculus and Beyond Homework Help
Replies
4
Views
458
• Calculus and Beyond Homework Help
Replies
7
Views
3K
• Calculus and Beyond Homework Help
Replies
30
Views
3K
• Calculus and Beyond Homework Help
Replies
1
Views
570
• Calculus and Beyond Homework Help
Replies
5
Views
866
• Calculus and Beyond Homework Help
Replies
2
Views
548
• Calculus and Beyond Homework Help
Replies
7
Views
492
• Calculus and Beyond Homework Help
Replies
7
Views
450
• Calculus and Beyond Homework Help
Replies
1
Views
750