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

Number theory: simple gcd question

  • #1

Homework Statement


If ax+by=1, then (a,b)=1.


Homework Equations





The Attempt at a Solution



I am just wondering if this is true. Because I know it is not true if ax+by=c, then (a,b)=c.

Here is a proof I came up with:

Suppose (a,b)=c, c>1.Then c|a and c|b, but then from our assumption, this implies that c|1, a contradiction.

I'm new to writing proofs so I just want to make sure I am on the right track. Thanks.
 

Answers and Replies

  • #2
dextercioby
Science Advisor
Homework Helper
Insights Author
12,985
540
It's ok. The proof is good.
 

Related Threads on Number theory: simple gcd question

Replies
2
Views
3K
  • Last Post
Replies
2
Views
424
  • Last Post
Replies
1
Views
2K
Replies
5
Views
494
  • Last Post
Replies
14
Views
2K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
1
Views
398
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
40K
Top