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$
  • 1
    $\begingroup$ what if 100! is in that interval? $\endgroup$ – Brent Aug 3 '15 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$ – Sandeep Silwal Aug 3 '15 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$ – Eric Wofsey Aug 3 '15 at 6:04
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.