MAT385-Proof by contraposition

[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
?
Any advice/guidance would be appreciated.

 

[gopher_p]

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
?
Any advice/guidance would be appreciated.

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.

 

[fritzh]

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

 

[fritzh]

Is this sufficient?

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

 

[gopher_p]

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

 

[fritzh]

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.

 

[gopher_p]

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.

 

[PeroK]

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
?
Any advice/guidance would be appreciated.

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.

 

[fritzh]

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