## Friday, 8 May 2020

### A question from number theory

Suppose $$n,a,d$$ be given integers and $$gcd (a,d)=1$$.  Prove that there exists an integer $$m$$ such that $$m\equiv a \mod d$$ and $$(m,n)=1$$?

1. This comment has been removed by the author.

2. Hint:- Even though there are easy solutions for this problem, what Dirichlet theorem on primes in arithmetic progression has to say on this?

3. Is this correct???

GIVEN : n, a , d are integers and gcd(a, d) =1

Since it is given that a and d are relatively prime, then by Dirichlet theorem the arithmetic sequence a, a+d, a+2d,...contain infinitely many primes

Let there be some a+dq in the sequence where q is an integer

Suppose a+dq=m_____(1)

Since a+dq lies in the sequence it is a prime and it will be an integer.
which implies there exist an integer m.

From(1)we have :

m=a+dq
Which implies, dq =m-a
And,    d divides (m-a)
This implies,   m congruent a (mod d)

since it is given that n is an integer and we found that there exist an integer m (which is also prime) therefore gcd (n, m) = 1

Hence proved

1. There are some gaps in the arguemment.
1. Are we taking q in with m=a+dq is prime?
2. If so, how can we ensure that $gcd(n,m)=1$?

4. There are two gaps in the argument.
1. Are we taking q with m=a+dq is prime?
2. If so, how can we ensure that gcd(n,m)=1?

1. Replace n in the place of q so that a+nd will be in the sequence where n is an integer

Then,
Suppose a+nd=m_____(1)

Since a+nd lies in the sequence it is a prime and it will be an integer.
which implies there exist an integer m.

From(1)we have :
m=a+nd
Which implies , dn =m-a
And,   d divides (m-a)
This implies,
m congruent a(mod d)

Since m is prime it is either divided by m or 1
This implies (a+nd) /m or (a+nd) /1

Case1:(a+nd) /m then  by the property of divisibiliy a/m  and nd/m,  but from this we cannot conclude that n/m or d/m

Case 2: (a+nd) /1 then by the property ofdivisibiliy a/1 and nd/1, this implies n/1 and we can conclude that n is also a prime.

As we have found that n and m are prime(provided m not equal to n)
gcd (m, n) =1

5. The idea is there are infinitely primes of the form $$a+qd$$ by Dirichlet theorem. Also the number $$n$$ has a finite number of prime factors. So choose a prime of the form $$m=a+qd$$ which is not a divisor of $$n$$. Done!

6. Here is the hint for a direct solution: Can we take $$q$$ as the product of all primes which divide's $$n$$ but not $$a$$?