1
$\begingroup$

(N.B. : The answer to the question was already given by both fleablood and gnasher729, so I'm just going to summarise a few points from this discussion for those who encounter problems like this in proof-writing.)
The problem I have encountered here is the confusion whether there exists a proof that there can be no number greater than the GCD of two numbers that divides them. I tried to prove it, but I did it the worng way, and hence ended up with a stupid write-up(LOL). So here are a few points for people to get away from puddles while proving.

  • One can't prove a definition using its properties, as a definition is self-explanatory and is also an abbreviation of the properties. As from gnasher729's answer, if $x$ is defined as the largest number with a property $X$, then it is obvious that no number $x' > x$ can have that property.
  • Trying to use a property of a number (here, $\gcd(a,b)$ and the property that $\gcd({{a}\over{\gcd(a,b)}},{{b}\over{\gcd(a,b)}}) = 1$) to prove its definition is useless as you are actually trying to use the property to prove itself and thus prove the definition, which is quite senseless and has no meaning. Therefore, try assuming the converse of that property (in this case, the GCD of the quotients is $1$) to try proving it (and still I won't get it in my case as GCD is defined to be so, which means negating the property and trying to prove is equivalent to saying that the GCD of $a$ and $b$ is another number greater than the one we take).

I didn't go for any formal training in number theory nor did I have time to learn fully from an online book that a forum member here offered me to take as a course, but I attempted the proof for "There exists no number greater than the GCD of $a$ and $b$ that divides both of them" by myself with the small amount of my knowledge in set theory and a bit on prime numbers. Here's how I did it, and I'd like anybody to tell me if I did it right or if I made a mistake.

The proof:

Let $\gcd(a,b) = d \implies a = dm, b = dn \space$ & $\space\gcd(m,n) = 1$
$ \exists k: k > d, k \mid a , k \mid b $
Let $pf(x) = \text{prime factors of a number} \space x \space$ $\text{considering each occurrence of a prime in the factorisation as a distinct one}$
$\because \gcd(a,b) = d, k \mid a \space \text{and} \space k \mid b, pf(d) \subseteq pf(k)$
$\implies k = ds , s >1 (\because k > d)$ $ \implies ds \mid a, ds \mid b$
$\implies s \mid m, s \mid n$
$\because \gcd(m,n) = 1 (i.e., pf(m) \cap pf(n) = \phi), s = 1$

Thus, $k \mid a \space\text{and}\space k \mid b$ only if $k = d$ (since $s = 1$ contradicts our assumption that $s > 1$).
$\therefore, \nexists k : k > \gcd(a,b), k \mid a, k \mid b$


The Result

As a result of posting this question, it seems to me that this will be a question for novices in proof-writing may view for reference on how to write proofs.

$\endgroup$
1
  • 1
    $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Pedro Tamaroff
    Jun 19 '21 at 11:09
1
$\begingroup$

Let $x$ be the largest number having a property $X$. Then no $x' > x$ has the property $X$, because if $x'$ had the property $X$, and $x' > x$, then $x$ wouldn't be the largest number with that property.

In your case the property $X$ is "is a common divisor of $a$ and $b$". The GCD of $a$ and $b$ is defined as the largest x with that property. Therefore no $x' > x$ can have that property. There's nothing to prove. We don't even have to look at anything about the GCD except that it is "the largest number with some property".

Go into a room with $50$ people. Find the tallest person in the room. Then I can guarantee that nobody in the room is taller. I don't have to measure anything, it's just obvious that nobody in the room can be taller than the tallest person in the room.

$\endgroup$
9
  • $\begingroup$ thanks but I didn't get you... I had rewritten the question as "Prove that there exists no number greater than the GCD of two numbers such that it divides both the numbers" $\endgroup$
    – Spectre
    Jun 17 '21 at 14:34
  • $\begingroup$ Secondly, we had been taught a proof in geometry that the perpendicular to a line from a point outside it is the shortest distance to it. If such proofs can exists, why can't this? Is it just because it is defined as such? $\endgroup$
    – Spectre
    Jun 17 '21 at 14:35
  • $\begingroup$ okay, now I get you, but why can't that proof exist? $\endgroup$
    – Spectre
    Jun 17 '21 at 14:37
  • 1
    $\begingroup$ Basically you are comparing this to trying to prove: "There is no shorter path from a line to a point not on the line then the path that has the shortest distance from line to that point." Or as gnasher729 puts it: "Prove that there is no person in a room that is taller than the tallest person in the room". $\endgroup$
    – fleablood
    Jun 18 '21 at 3:53
  • 1
    $\begingroup$ 1) There is utterly no point in proving something you already know. ANd you know it is true by definition 2) The only reason you know it has those properties is because you proved that if there is not larger common divisor than $d$ then $\frac ad \frac bd$ have no divisor larger than $1$ in common. So if you tried to use that to prove what you had to assume in the first place to prove the property you are going around in circles. $\endgroup$
    – fleablood
    Jun 18 '21 at 6:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.