Greatest Common Divisor Proof

  • Thread starter hoopsmax25
  • Start date
  • #1
13
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.
 

Answers and Replies

  • #2
294
1
Well we clearly have a|a and a|b, and the largest divisor of a number is itself. This should follow immediately.
 
  • #3
13
0
Yeah and i understand that but we are asked to prove it, not explain why.
 
  • #4
294
1
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.
 
  • #5
294
1
The difference between a proof and an explanation actually becomes increasingly fuzzy the farther you get in math.
 
  • #6
22,129
3,297
A proof of this is certainly possible.

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

Related Threads on Greatest Common Divisor Proof

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
24
Views
3K
  • Last Post
Replies
2
Views
896
  • Last Post
Replies
5
Views
1K
Replies
11
Views
4K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
8
Views
1K
Replies
7
Views
2K
  • Last Post
Replies
19
Views
5K
Replies
2
Views
1K
Top