1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

B Consecutive integers, each relatively prime to some k

  1. Apr 8, 2016 #1

    Say I have some integer n in some interval such that,
    gcd(n, k) = gcd(n + 1, k) = 1, for some composite odd integer k >= 9
    I want to know if such n exists in that interval. To know that one exists suffices.

    I have tried to think in terms of modular arithmetic where for all primes in k, the smaller of which is "embedded" inside the larger one: e.g. given two primes 5 and 13, the latter determines the outer "clock" while, begining from zero, number 5 puts marks on that clock (which uses arithmetic modulo 13). For some obvious reasons, this got really complicated...

    I'm not sure either whether writing out a linear combination for each gcd will lead somewhere.

    I'm not expecting a full solution. I just need some guidance (or to know whether this is solvable at all).
  2. jcsd
  3. Apr 8, 2016 #2


    User Avatar
    Science Advisor
    Gold Member

    gcd(k,k+1)=1 for all k∈ℤ. Start with n=k+1 and try to find a k such that gcd(k,k+2)=1

    Edit: Sorry, I think I misread your post. Are you looking for a specific example, or are you looking for a general test?
  4. Apr 8, 2016 #3


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The question is unclear. What is the interval you are asking about, and what role does it play in the question?

    Certainly we can find integers n and k that satisfy your equation, for instance:

    n=5, k=91=13x7 gives gcd(5,91)=gcd(6,91)=1
  5. Apr 9, 2016 #4
    Here is an example:

    Show that,
    gcd(x, 5005) = gcd(x + 1, 5005) = 1 is true for some x,
    where 2085 < x < 2110 and 5005 = 5*7*11*13

    (Numbers 2085 and 2110 are not totally arbitrary.)

    I need to show that it's true, in a general way. I'm not looking for a method "similar" to the sieve of Eratosthenes; not an algorithm, where the output of which is examined for each input. It's easy to prove the above example by using a program, but that method is not general.

    Hopefully I made it more clear...
  6. Apr 9, 2016 #5


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    It is not true in general. For instance there is no x such that
    gcd(x, 105) = gcd(x + 1, 105) = 1
    13 < x < 16.

    To get a provable proposition, you will need to introduce some constraints on what the bounds of the interval may be. You said that the bounds in your example were not totally arbitrary. Are you able to work out a rule for what sorts of bounds you wish to consider?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted