Number Theory: Simple Divisibility & GCD

  • #1
doubleaxel195
49
0

Homework Statement


Prove that if N=abc+1, then (N,a)=(N,b)=(N,c)=1.


Homework Equations





The Attempt at a Solution


Assume N=abc+1. We must prove (N,a)=(N,b)=(N,c)=1. Proceeding by contradiction, suppose (N,a)=(N,b)=(N,c)=d such that [tex] d\not=1 [/tex]. Then we know, d | N and d | abc. Thus, from our assumption, we see that d | 1, a contradiction.

Is this a valid argument? Also, what is another way to prove this without using contradiction? Thanks, this is my first class with proofs. Also, I know "if (a,b)=d, then ax+by=d." Is the converse true?
 

Answers and Replies

  • #2
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,129
3,302
Yes, this is a valid argument.

And the converse is not true: consider 9.1+7.(-1)=2, but (9,7) is not 2...
 
  • #3
doubleaxel195
49
0
Thank you very much!
 

Suggested for: Number Theory: Simple Divisibility & GCD

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
14
Views
2K
  • Last Post
Replies
1
Views
587
  • Last Post
Replies
2
Views
660
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
2
Views
811
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
1
Views
1K
Top