Number theory: gcd(a,b)=1 => for any n, gcd(a+bk,n)=1 for some k

  • #1

Homework Statement


[itex]a[/itex] and [itex]b[/itex] are coprime. Show that for any [itex]n[/itex], there exists a nonzero integer [itex]k[/itex] that makes [itex]a+bk[/itex] and [itex]n[/itex] coprime.


Homework Equations


[itex]a[/itex] and [itex]b[/itex] are coprime if any of the following conditions are met:
  1. [itex]\text{gcd}(a,b)=1[/itex]
  2. the ideal [itex](a,b)=\{ax+by : x,y\in\mathbb{Z}\}[/itex] is equal to the set of all integers [itex]\mathbb{Z}[/itex]


The Attempt at a Solution


I tried expanding the desired result in terms of ideals:
[itex](a+bk,n) = \{(a+bk)x+ny : x,y\in\mathbb{Z}\} = \{ax+bkx+ny : x,y\in\mathbb{Z}\}[/itex]

If [itex]a[/itex] and [itex]n[/itex] are coprime, then setting [itex]k=0[/itex] makes [itex]a+bk[/itex] and [itex]n[/itex] coprime.

I couldn't figure out the case where [itex]a[/itex] and [itex]n[/itex] have a gcd other than 1.
 
Last edited:

Answers and Replies

  • #2
morphism
Science Advisor
Homework Helper
2,015
4
If a and n have gcd other than 1 then there will be a prime p dividing both of them. Now suppose that p divides a+bk. What can you say now?
 

Related Threads on Number theory: gcd(a,b)=1 => for any n, gcd(a+bk,n)=1 for some k

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
688
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
1
Views
459
  • Last Post
Replies
2
Views
498
  • Last Post
Replies
14
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
3K
Top