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

In summary, the problem is to show that for any n, there exists a nonzero integer k such that a+bk and n are coprime. This can be expanded in terms of ideals, where (a+bk,n) is the set of all integers that can be expressed as (a+bk)x+ny. If a and n are coprime, setting k=0 makes (a+bk,n) equal to (a,n), which is equal to the set of all integers. However, if a and n have a common prime factor, p, then p must also divide a+bk for some integer k. This case requires further investigation.
  • #1
Just a nobody
13
0

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:
Physics news on Phys.org
  • #2
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?
 

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

What is the significance of gcd(a,b)=1 in number theory?

The greatest common divisor (gcd) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. When the gcd of two numbers is 1, it means that the two numbers are relatively prime, or have no common factors other than 1. This is significant in number theory because it is the basis for many important theorems and algorithms.

How does gcd(a,b)=1 relate to the equation gcd(a+bk,n)=1?

The equation gcd(a+bk,n)=1, where k is any integer, means that for any integer n, there exists a value of k that makes the gcd of a+bk and n equal to 1. In other words, adding any multiple of b to a results in a number that is relatively prime to n. This is a property known as Bézout's lemma and is closely related to the Chinese remainder theorem.

What is the practical application of the statement gcd(a,b)=1 => for any n, gcd(a+bk,n)=1 for some k?

This statement has many practical applications in number theory and cryptography. For example, it can be used to show that there are infinitely many prime numbers, as any number n can be expressed as n=2k+1 where k is an integer. This allows for the creation of algorithms that can efficiently generate large prime numbers.

Can the statement gcd(a,b)=1 => for any n, gcd(a+bk,n)=1 for some k be extended to more than two numbers?

Yes, this statement can be extended to any number of integers. If the gcd of a set of numbers is 1, then for any integer n, there exists a set of values for k that make the gcd of the sum of the numbers and n equal to 1. This is known as the coprimality property and is a fundamental concept in number theory.

Are there any exceptions to the statement gcd(a,b)=1 => for any n, gcd(a+bk,n)=1 for some k?

No, there are no exceptions to this statement. As long as the initial conditions of gcd(a,b)=1 are met, the equation gcd(a+bk,n)=1 will hold true for any integer n and some value of k. This is a fundamental property of relatively prime numbers and is a well-established concept in number theory.

Similar threads

Prove if ##a\cdot c = b \cdot c## then ##a = b## using Peano postulates
Replies
2
Views
834
Prove ##1 + a=s(a)=a+1## for ##a \in \mathbb{N}##
Replies
1
Views
982
Prove ##a \cdot 1 = a = 1 \cdot a## for ##a \in \mathbb{N}##
Replies
1
Views
1K
Prove ##(a+b)\cdot c=a\cdot c+b\cdot c## using Peano postulates
Replies
3
Views
1K
Prove ##(a+b) + c = a + (b+c)## using Peano postulates
Replies
9
Views
2K
Prove that ## \sqrt{p} ## is irrational for any prime ## p ##?
Replies
5
Views
2K
Each integer n>11 can be written as the sum of two composite numbers?
Replies
7
Views
3K
Prove ##(a\cdot b)\cdot c =a\cdot (b \cdot c)## using Peano postulates
Replies
1
Views
859
Prove ##a + b = b + a## using Peano postulates
Replies
3
Views
1K
Number theory GCD relatively prime question
Replies
5
Views
1K

Hot Threads

Recent Insights

Back
Top