What is the proof for a = gcd(a, b) when a|b?

Click For Summary

Homework Help Overview

The discussion centers around proving the statement that if \( a \) divides \( b \) (denoted as \( a|b \)), then \( a \) is equal to the greatest common divisor (gcd) of \( a \) and \( b \). The subject area involves number theory and properties of divisibility.

Discussion Character

  • Exploratory, Conceptual clarification, Assumption checking

Approaches and Questions Raised

  • Participants discuss the intuitive nature of the statement and explore various approaches to formalize the proof, including using the definition of gcd and considering proof by contradiction. Questions arise regarding the expectations for the proof's formality and the definitions of divisibility and gcd.

Discussion Status

The discussion is ongoing, with participants offering different perspectives on how to approach the proof. Some express confidence in the simplicity of the statement, while others emphasize the need for a rigorous proof and clarification of definitions.

Contextual Notes

There is mention of the need to clarify how \( a|b \) and \( \text{gcd}(a,b) \) are defined, indicating that these definitions may influence the proof process.

hoopsmax25
Messages
13
Reaction score
0

Homework Statement



Suppose a, b ∈ N and a|b. Prove that a = gcd(a, b).

Homework Equations


Seems easy intuitively but actually proving it is giving me problems.


The Attempt at a Solution


I have been trying to use the fact that gcd(a,b)=na + mb here m and n are integeres but got stuck.
 
Physics news on Phys.org
Well we clearly have a|a and a|b, and the largest divisor of a number is itself. This should follow immediately.
 
Yeah and i understand that but we are asked to prove it, not explain why.
 
Well you can probably prove by contradiction that the largest divisor of a number is itself. I mean a|b => a=gcd(a,b) is so trivial that there's very little to say, how formal does your professor expect your proof to be? You can take it all the way down to pure logic if you really wanted to.
 
The difference between a proof and an explanation actually becomes increasingly fuzzy the farther you get in math.
 
A proof of this is certainly possible.

But first, we would have to know how exactly you defined a|b and gcd(a,b).
 

Similar threads

Replies
2
Views
2K
  • · Replies 4 ·
Replies
4
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 8 ·
Replies
8
Views
5K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 1 ·
Replies
1
Views
1K
Replies
1
Views
2K