2
$\begingroup$

For an arbitrary integer $n$ define $A_n=\{i|n \leq i \leq n+99 \text{ where }i\text{ is an integer}\}$ (i.e. $A_n$ is 100 consecutive integers)

Is it true that for any integer $n$ there is an element in $A_n$ which is relatively prime to all numbers in $A_1$?

Thanks

$\endgroup$
3
  • 1
    $\begingroup$ what if 100! is in that interval? $\endgroup$
    – Brent
    Aug 3, 2015 at 4:03
  • $\begingroup$ @Brent: Then either $100!-1$ or $100!+1$ will also be in that interval and those are relatively prime to everything in $A_1$. $\endgroup$ Aug 3, 2015 at 4:05
  • $\begingroup$ Replacing $N=100$ with smaller numbers and doing some calculations, it seems likely that this is false for any $N>10$. Proving this seems like it would be nontrivial, though. For $N=100$, it looks like a tedious but feasible computation: by the Chinese remainder theorem, you are allowed to distribute the multiples of different primes $p<100$ in $A_n$ independently of each other; now you just want to come up with some choices so that their multiples cover all of it. $\endgroup$ Aug 3, 2015 at 6:04

2 Answers 2

4
$\begingroup$

Here is an explicit construction of an $A_n$ which fails to have an element that is relatively prime to all the elements in $A_1$. The idea behind this construction is as follows. $$A_n = \{n, n+1, n+2, \cdots, n+99\}.$$ Now we want to "spread" the $25$ primes in $A_1$ well enough such that everything in $A_n$ is congruent to $0 \pmod p$ for atleast one prime in $A_1$. Furthermore, if we assign $n+k \equiv 0 \pmod p$ for some $0 \le k \le 99$, then for all $m \equiv k \pmod p$, $n+m \equiv 0 \pmod p$ since $$n+m \equiv n+k \equiv 0 \pmod p.$$ Once I have assigned $n+k \equiv 0 \pmod p$, I look at the next value of $k$ (say $k'$) that is not already covered and assign $n+k' \equiv 0 \pmod p'$ where $p'$ is the next largest prime in $A_1$ after $p$. My construction is as follows.

$$n \equiv 0 \pmod {2\cdot 3 \cdot 13 \cdot 17}, \quad n + 1 \equiv 0 \pmod 5$$ $$n + 7 \equiv 0 \pmod {11}, \quad n + 23 \equiv 0 \pmod {19}$$ $$n + 25 \equiv 0 \pmod {23}, \quad n + 35 \equiv 0 \pmod {29}$$ $$n + 37 \equiv 0 \pmod {31}, \quad n + 43 \equiv 0 \pmod {37}$$ $$n + 49 \equiv 0 \pmod {41}, \quad n + 53 \equiv 0 \pmod {43}$$ $$n + 55 \equiv 0 \pmod {47}, \quad n + 59 \equiv 0 \pmod {53}$$ $$n + 65 \equiv 0 \pmod {59}, \quad n + 67 \equiv 0 \pmod {61}$$ $$n + 77 \equiv 0 \pmod {67}, \quad n + 79 \equiv 0 \pmod {71}$$ $$n + 83 \equiv 0 \pmod {73}, \quad n + 97 \equiv 0 \pmod {79}.$$

Mathematica gives the smallest value of such an $n$ to be $2479447854547486799186954214354$ and the following Python program quickly checks that this $n$ does indeed work. We could possibly generalize this question to ask for what size of $A_1$, do the translates of $A_1$ have this "gcd" property? The user catfish showed that $4$ has this property while $100$ does not. Interestingly enough, if we start out with $n \equiv 0 \pmod 2$ in my construction, it is not possible to find an $n$ so there has to be an underlying story behind why the first term needs to have more than $1$ prime factor in $A_1$.

L = []
for k in range(2479447854547486799186954214354, 2479447854547486799186954214354+100):
    L.append(k)
P = [2, 3, 5, 7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97 ]

while len(P) > 0:
    for k in L:
        if  k% P[0] == 0:
            L.remove(k)
    P.remove(P[0])

print (len(L))
$\endgroup$
-1
$\begingroup$

If we assume $0$ is relatively prime to all integers, perhaps we can use the Chinese remainder theorem to see more. Let $n\in\mathbb{Z}$. An element $m\in A_{n}$ will be relatively prime to all of $A_{1}$ iff it has nonzero remainder modulo every prime in $A_{1}$.

This gives a system of congruences $$ m \equiv a_{1} (\bmod p_{1})\\ ...\\ m \equiv a_{N} (\bmod p_{N}) $$

where $p_{1},...,p_{N}$ are the primes in $A_{1}$, and $a_{1},...a_{N}\neq 0$. Let $M = p_{1}\cdots p_{N}$. Then by the Chinese remainder theorem, $m = (a_{1}b_{1}\frac{M}{p_{1}} + ... + a_{N}b_{N}\frac{M}{p_{N}}) + tM$ for some $t\in\mathbb{Z}$. (here each $b_{i}$ is $a_{i}^{-1}$ taken in $\mathbb{Z}/p_{i}\mathbb{Z}$)

So I think a way to find the answer is to consider the set $B$ of smallest positive values of $a_{1}b_{1}\frac{M}{p_{1}} + ... + a_{N}b_{N}\frac{M}{p_{N}} + tM$ for all $a_{1},...a_{N}\neq 0$ and then make sure that $\forall b\in B$ $\exists c\in B$ with $|b-c|\leq 100$. If this is the case, then the answer is affirmative, if not, then the answer is negative (this is because $\forall b\in B$, $b+tM \not\equiv 0 (\bmod p_{i})$ $\forall i$, that is, $b+tM$ is relatively prime to all of $A_{1}$ $\forall t\in\mathbb{Z}$). For your definition of $A_{n}$, $|B| = (p_{1}-1)\cdots (p_{N}-1) = 277 399 690 427 737 839 953 078 806 118 400 000$ though...

We could do this for a much simpler scenario; suppose we define $A_{n} = \{i | n\leq i\leq n + 3\}$. The primes in $A_{1}$ are $2,3$, and the nonzero values of $a = (a_{1},a_{2})$ are $(1,1)$ and $(1,2)$, and $B = \{1,5\}$. Here $M = 2\cdot 3 = 6$. Since the distance between $1,5$ is $4$ and so not strictly greater than $4$, and since all translates of $1,5$ by multiples of $6$ will have nonzero remainder modulo all primes of $A_{1}$, all such translates will be relatively prime to every element of $A_{1}$. So for any $A_{n}$, there will be an element of $A_{n}$ relatively prime to all of $A_{1}$.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .