• Support PF! Buy your school textbooks, materials and every day products Here!

Discrete math (gcd)

  • Thread starter Miike012
  • Start date
  • #1
1,011
0
Corollary from book:

if d= gcd(a,b), then there exists integers x and y such that ax + by = d.

This is not an obvious statement to me. Are there any direct proofs to prove this statement? The book proves this by induction.

My proof:
Suppose d = gcd(a,b) and a and b are positive integers. a does not necessarily divide b and b does not necessarily divide a so

let qa and ra be integers such that a = qab + ra. If d|a then d|(qab + ra) therefore d|ra, that is there exists an integer Ra such that ra = Rad.

Let qb and rb be integers such that b = qba + rb. We can see d|rb so Let Rb be the integer such that rb = Rbd.

now
a + b = qab + qba + (Ra + Rb)d and
a(1-qb)/(Ra + Rb) + b(1-qa)/(Ra + Rb) = d.

Now I just need to prove that the coef. of a and b are integers...
 
Last edited:

Answers and Replies

  • #2
verty
Homework Helper
2,164
198
The extended Euclidean algorithm calculates those coefficients, so one avenue is an invariant-based proof based on that algorithm. Otherwise, a proof by contradiction should be doable.
 

Related Threads on Discrete math (gcd)

  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
9
Views
12K
  • Last Post
Replies
4
Views
847
  • Last Post
Replies
4
Views
5K
  • Last Post
Replies
2
Views
8K
Top