# B Consecutive integers, each relatively prime to some k

1. Apr 8, 2016

### r731

Hello,

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).
Thanks.

2. Apr 8, 2016

### TeethWhitener

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?

3. Apr 8, 2016

### andrewkirk

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

4. Apr 9, 2016

### r731

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...

5. Apr 9, 2016

### andrewkirk

It is not true in general. For instance there is no x such that
gcd(x, 105) = gcd(x + 1, 105) = 1
and
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?