7
$\begingroup$

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$?

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ Jan 8, 2016 at 15:28
  • 5
    $\begingroup$ Question 1 is true for powers of odd primes, hence for all n by the Chinese Remainder Theorem. $\endgroup$ Jan 8, 2016 at 15:37
  • $\begingroup$ 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. $\endgroup$
    – C0nn0t
    Jan 8, 2016 at 15:52
  • $\begingroup$ In question 1 we may really take $|\mathcal{S}|=1$. In question 2, do we still need this or not? $\endgroup$ Jan 8, 2016 at 17:15
  • $\begingroup$ 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?$ $\endgroup$
    – C0nn0t
    Jan 9, 2016 at 18:18

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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.... $\endgroup$ Jan 12, 2016 at 2:39
  • 1
    $\begingroup$ $n$ is odd, is not it? $\endgroup$ Jan 12, 2016 at 7:16
  • $\begingroup$ N is indeed odd. Thank you Fedor! I marked your answer as a solution. $\endgroup$
    – C0nn0t
    Jan 12, 2016 at 20:22
  • $\begingroup$ 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$. $\endgroup$
    – C0nn0t
    Jan 13, 2016 at 17:31
  • 1
    $\begingroup$ @GregMartin When $n$ is even then every even $l$ is a counterexample ;) $\endgroup$
    – Nick S
    Jan 13, 2016 at 18:18
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ Jan 14, 2016 at 3:42
  • $\begingroup$ 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 $\endgroup$ Jan 14, 2016 at 3:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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