# Adding coprimes to get a coprime

These questions arose in my research. Let $n$ be odd and let $\mathcal{C}_n$ be the set of integers less than $n$ which are coprime with $n$.

Question 1: For each integer $\ell: 0 \leq \ell < n$ can we always find a subset $\mathcal{S} \subset \mathcal{C}_n$ such that $$\ell+2\cdot\sum_{c \in \mathcal{S}}c \quad (\textrm{mod } n)$$ is coprime with n? That is, can we always find some set of numbers coprime with $n$ such that twice their sum added to $\ell$ is coprime with $n$? Can we always get $|\mathcal{S}| = 1$ when $\ell$ is not coprime with $n$?

Question 2: What is the smallest set $\mathcal{B_n} \subset \mathcal{C}_n$ such that Question 1 holds with $\mathcal{C}_n$ replaced by $\mathcal{B}_n$?

• Exactly which statement do you mean in Question 2? You use the set of coprime numbers more than once. Do you mean to replace both with the same set, or just one? – Douglas Zare Jan 8 '16 at 15:28
• Question 1 is true for powers of odd primes, hence for all n by the Chinese Remainder Theorem. – Douglas Zare Jan 8 '16 at 15:37
• I reformatted the question. It seems to be enough to let $\mathcal{B}_n$ be all powers of 2 less than $n$ and then the statement holds. I'm not sure if we can do better. – C0nn0t Jan 8 '16 at 15:52
• In question 1 we may really take $|\mathcal{S}|=1$. In question 2, do we still need this or not? – Fedor Petrov Jan 8 '16 at 17:15
• In question 2 I'm more interested in just finding a $\mathcal{B}_n$ with a nice structure and as small as possible preferrably. How do we get $|\mathcal{S}| = 1?$ – C0nn0t Jan 9 '16 at 18:18

This is extended Douglas Zare's comment explaining why we may take $|S|=1$. We prove that for any residue $\ell$ modulo $n$ there exist $a,b$ coprime to $n$ such that $\ell+a \equiv b \pmod n$. Then we may take $S=\{a/2\}$.

For any prime $p$ which divides $n$ choose remainder $a_p$ modulo $p$ such that neither $a_p$, nor $a_p+\ell$ is divisible by $p$. This is clearly possible, there are (at least) $p-2$ ways to do it. Then by Chinese Remainders Theorem there exists $a$ congruent to $a_p$ modulo each $p|n$. Use it.

As for the question 2, we may take ${\mathcal B}_n$ with $k$ elements, where $k$ is the number of distinct prime divisors of $n$ (this is in general better than powers of 2 not exceeding $n$). For any $p|n$ choose a number $b(p)$ such that $2b(p)$ gives remainder 2 modulo $p$ and 1 modulo other prime divisors of $n$. Fix $\ell$ and for $m=0,1,\dots$ denote by $f(m)$ the number of primes $p|n$ for which $p|\ell+m$.

Lemma. Assume that $f(m)\leqslant m$ and $f(m+1)\leqslant k-m$. Then there exists a set $A$, $|A|=m$, of prime divisors of $n$, such that $\ell+\sum_{p\in A} 2b(p)$ is coprime to $n$.

Proof. Denote $x=\ell+\sum_{p\in A} 2b(p)$. Then $x\equiv \ell+m+\chi_A(p) \pmod p$ for all prime $p|n$. So, there are $f(m)$ primes which have to be included to $A$ and $f(m+1)$ other primes which can not be included. Clearly such $A$ exists exactly when $f(m)\leqslant m$ and $f(m+1)\leqslant k-m$.

Now we need to find appropriate $m$. It is not a big deal, since we always have $f(m)+f(m+1)\leqslant k$ and $f(m)+f(m+2)\leqslant k$.

If $k$ is even, $k=2q$, we examine $m=q-1$ and $m=q$. Assume that both do not work. If $f(q)\leqslant q$, then $f(q-1)\geqslant q+1$, $f(q+1)\geqslant q+1$, a contradiction. If $f(q)\geqslant q+1$, then both $f(q+1)\leqslant q-1$ and $f(q+2)\leqslant q-1$ and we may take $m=q-1$.

If $k=2q-1$, consider $f(q)$. If $f(q)\leqslant q$, then $f(q-1)\geqslant q$ (else $m=q-1$ works) and $f(q+1)\geqslant q$ (else $m=q$ works). A contradiction. If $f(q)\geqslant q+1$, then $f(q+1)\leqslant q-2$, $f(q+2)\leqslant q-2$, so $m=q+1$ works.

• This is clearly the right approach, and works when $n$ is odd. But if $2\mid n$, then "at least $2-2$ ways" isn't enough.... – Greg Martin Jan 12 '16 at 2:39
• $n$ is odd, is not it? – Fedor Petrov Jan 12 '16 at 7:16
• N is indeed odd. Thank you Fedor! I marked your answer as a solution. – C0nn0t Jan 12 '16 at 20:22
• I started to doubt the solution to Question 2. Tell me if I'm missing something, but if $b(p)$ is 0 modulo some prime divisors of $n$, then it won't be coprime with $n$? Therefore $\mathcal{B}_n$ wont be a subset of $\mathcal{C}_n$. – C0nn0t Jan 13 '16 at 17:31
• @GregMartin When $n$ is even then every even $l$ is a counterexample ;) – Nick S Jan 13 '16 at 18:18

To make up for my not-well-thought-out comment to Fedor Petrov's answer, here is an answer to show $B$ can have $O((\log k)^2)$ elements, where $k$ is the number of distinct prime factors of $n$. If one pursues the literature, one can take this down to $O(\log k)$ elements.

$n$ being odd, $2$ and its powers are coprime to $n$, with $d=(n+1)/2$ being a multiplicative inverse mod $n$. Now $\gcd(l+2b,n)=\gcd(dl+2db,n)=\gcd( c+b,n)$, so we just need to find the greatest distance between an arbitrary number $c$ and the next largest coprime integer $c+b$. More simply put, $l+2i$ is coprime to $n$ for at least one $i$ greater than $0$ and less than a value which I will call $g(n)+1$.

This is related to Jacobsthal's function $g(n)$, of which I know a little something. One has $g(n) \leq k^{A + C\log\log k}$, where $A,C \lt 4$, which can be found in an arxiv preprint (cf MathOverflow 37679), which lets us take $B$ to be the powers of 2 from 1 up to $\log(g(n))$, giving fewer than $O((\log k)^2)$ elements.

Gerhard "Sorry For Not Thinking Earlier" Paseman, 2016.01.13

• By considering $2^j$ instead of $2$, it might be possible to construct a B of similar size, but where just one or two elements of B are needed for the sum. I will put this on my "To Think" list. Gerhard "Put On Your List Too" Paseman, 2016.01.13 – Gerhard Paseman Jan 14 '16 at 3:42
• Also note that 2 in the problem can be replaced with a fixed number t such that t is coprime to n, and the same set B will still work. An analogous set will work for even n and appropriate t. Gerhard "Likes To Anticipate Easy Generalizations" Paseman, 2016.01.13 – Gerhard Paseman Jan 14 '16 at 3:52