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\)?

8 comments:

  1. This comment has been removed by the author.

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

    ReplyDelete
  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

    ReplyDelete
    Replies
    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$?

      Delete
  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?

    ReplyDelete
    Replies
    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

      Delete
  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!

    ReplyDelete
  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\)?

    ReplyDelete