# The difference set $D(\mathbb Z^*_n)$ of $\mathbb Z_n^*$

I wish to ask whether $D(\mathbb Z^*_n)=\mathbb Z_n^+$ given $n$ is odd.

This is equivalent to proving that: For every $l\in\mathbb Z^+_n$, the set $l+\mathbb Z^*_n=\{a+l:a\in\mathbb Z^*_n\}\subset\mathbb Z^+_n$ intersects $\mathbb Z^*_n$ in a non-empty set.

Where $|\mathbb Z^*_n|>\frac12|\mathbb Z^+_n|$ this is quite easily seen, for there cannot be two disjoint sets, in any set $A$ each with cardinality more than half that of $A$.

But this cardinality inequality does NOT always hold. In fact $|\mathbb Z^*_n|$ as a fraction of $|\mathbb Z^+_n|$ can get arbitrarily tiny, as $n$ can have an arbitrarily large number of distinct prime factors! This therefore paves way for $l+\mathbb Z^*_n$ to be disjoint from $\mathbb Z^*_n$, for some $l\in\mathbb Z^+_n$, thereby disproving the statement on the first line.

The smallest $n$ where the fraction $\displaystyle\frac{|\mathbb Z^*_n|}{|\mathbb Z^+_n|}$ is below half is $n=105$, where, however, the statement on line one holds true still!

Another thing noted is when $(l,n)=1$. Then definitely $(2l,n)=1$. Then $l$ occurs as the difference of $2l$ and $l$, so that $D(\mathbb Z^*_n)$ contains $\mathbb Z^*_n$ surely.

UPDATE: The cardinality of $D(\mathbb Z^*_n)$ can't exceed $\phi(n)^2-\phi(n)+1$, as the differences $a-a$ are all $0$, and are to be counted as one.

Need help!

P.S. An equivalent (ring theoretic) version is the following:

In the ring $\mathbb Z_n$ of integers modulo $n$, can every element be written as the difference of two units? Can ring theory chip in?

• What is $\mathbb{Z}^+_n$? Commented Apr 15, 2014 at 7:37
• The additive group modulo $n$. Also $\mathbb Z^*_n$ is the multiplicative group consisting of $0<a\le n$ such that $(a,n)=1$ Commented Apr 15, 2014 at 7:38
• What is the map $D$ ? Commented Apr 15, 2014 at 9:01
• $D(A)$ denotes the difference set of $A$. The set of all $a-b$ with $a,b\in A$. Instead of the usual subtraction, we have subtraction modulo $n$. Commented Apr 15, 2014 at 10:20
• @AneeshKarthikC: Regarding your update: Sorry, but $\phi(n)^2>n$ for all odd $n>1$. This can be seen e.g. by induction on the number of prime factors of $n$. Commented Apr 15, 2014 at 13:39

Yes, this is true. An equivalent formulation is: for every integer $d$ and every odd integer $n$, there exists an integer $u$ such that both $u$ and $u+d$ are relatively prime to $n$. The key observation is that if this is true when $n$ is an odd prime power, then it's true for all odd $n$ by the Chinese remainder theorem. And when $n=p^k$ is an odd prime power, then it suffices to choose $u\not\equiv0,-d\pmod p$, which is possible since $p\ge3$.
• Indeed I had thought about Chinese Remainder Theorem but setting the right residue classes was a problem. you nailed it by setting it to not equalling $0$ or $-d$! Commented Apr 16, 2014 at 5:31
• Thanks :) In fact this solution allows you to count the number of representations of $d\in\Bbb Z_n^+$ as a difference of two elements of $\Bbb Z_n^*$: it's $$n\prod_{p\mid(d,n)}\bigg(1-\frac1p\bigg)\prod_{\substack{p\mid n\\p\nmid d}}\bigg(1-\frac2p\bigg).$$ For that matter, this formula holds when $n$ is even as well. Commented Apr 16, 2014 at 5:46
• Oh yes! Thanks a lot :-) Yes, if $d$ is odd and $n$ even, one term in the latter product is zero and kills the product! Commented Apr 16, 2014 at 5:50