0

If this proof is incorrect can someone tell me what is wrong with it, and which step is incorrect.

Let a, b ∈ℤ

If gcd(a, b) = 35, then 25 ∤ a or 25 ∤ b.

Proof

  1. Consider the contrapositive: if 25|a and 25|b, then gcd(a,b) ≠ 35.

  2. Let d = gcd(a,b)

  3. Assume 25|a and 25|b

  4. Assume for the sake of contradiction that d=35

  5. Since 7|35 therefore 7 must be a common factor of a and b

  6. Since 25 is also a common factor of a and b, and gcd(7,25) = 1, therefore by problem 4, (7)(25)=175 is another common factor of a and b as well.

  7. But 175>35, which violates the definition of GCD (contradiction)

Jake Park
  • 1,277
  • I think the proof is correct. It is allready enough to observe that $25|a$ and $25|b$ implies that $25|gcd(a,b)$ wich is not the case if $gcd(a,b)=35$. Involving factor $7$ is redundant, but not wrong. – drhab Oct 15 '13 at 19:09

1 Answers1

1

Hint: $d\mid a\wedge d\mid b\Rightarrow d\mid\gcd\left(a,b\right)$

drhab
  • 151,093
  • Does that mean the proof is incorrect? – Jake Park Oct 15 '13 at 19:23
  • No, the proof is is correct (as I remark in my comment). It is enough however to observe that $25$ is a common factor of $a$ and $b$ on base of point 3. You do not need factor $7$, but your reasoning stays correct. – drhab Oct 15 '13 at 19:25
  • Would this be considered as proof by contrapositive or proof by contradiction? – Jake Park Oct 15 '13 at 19:31
  • Your prove in whole both contrapositive and contradiction. But the contradiction part can be left out. As I said you do not need factor $7$, so you do not need assumption 4. Is is enough to say that 3. leads to $25|gcd(a,b)$ so that $gcd(a,b)$ cannot equalize $35$. – drhab Oct 15 '13 at 20:01
  • If this is meant to be a proof characterized by contradiction then I would reject it. Looking for such a thing (the tags of your question make me see that as possible)? Prove for instance that the set of primes is not finite. – drhab Oct 16 '13 at 08:27