How do you prove a biconditional statement using the contradiction method?

Question

I have to prove the following by method of contradiction:

Let p and q be positive integers with p a) Prove that q-p divides p-1 if and only if q-p divides q-1.
b) Let d be a common divisor of p-1 and q-1. Prove that d divides q-p.

I understand the concept behind proving if, then statements by contradiction (assume the "if..." and also assume the not "then..." then reach a contradiction) but I'm confused as to how to do it for an if and only if problem.

Answer 1

a) The solution seems mysterious, until it smacks you in the face like a giant smacking thing (yes, I _do_ need to work on my analogies). Suppose (q-p) | (p-1). Then ∃k∈Z such that k(q-p) = p-1. Adding q-p to both sides yields (k+1)(q-p) = q-1, so (q-p) | (q-1). Conversely, (q-p) | q-1 ⇒ ∃k∈Z s.t. k(q-p) = q-1 ⇒ ∃k∈Z s.t. (k-1)(q-p) = p-1 ⇒ (q-p) | (p-1).

b) Suppose d|(p-1) and d|(q-1). Then ∃k₁, k₂ s.t. k₁d = p-1 and k₂d = q-1, so (k₂ - k₁)d = (q-1) - (p-1) = q-p, so d|(q-p).

I'm not sure why your teacher asked you to use an indirect proof here -- as you can plainly see, the direct proofs are so much simpler. I wonder what she actually had in mind...

Answer 2

Let p and q be positive integers with p assume that you have already proven a)
thus that p-1 | q-p <=> q-p | q-1

<=> means that if and only if. that is p-1 | q-p implies q-p | q-1
and q-p | q-1 implies p-1 | q-p.

with a) that you can easily prove b).

so the only thing you need to prove is a)

Answer 3

definitely, what you're saying is mistaken. that's a similar because of the fact the around sq. state of affairs. If the object in question negates itself by ability of definition, there is not any actual premise. consequently you're no longer proving the non-existence of a few thing. All you're doing is arising some thing that's impossible to exist for the only objective of proving its non-existence. that's no longer a information, fellow atheist. that's only fancy communicate.

Answer 4

Biconditional Proof

Answer 5

A <=> means

A => B and B => A.

The negation of this disjunction is:

(A and ~B) or (B and ~A), where '~' means not.

So a prove by contradiction only requires one of the above, ie, assume (A and ~B), and get a contradiction, or
assume (B and ~A) and get a contradiction.

You only need one.

Answer 6

Treat them as two separate conditional statements. First, you prove A→B, and then you prove B→A.