1
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ What is $\mathbb{Z}^+_n$? $\endgroup$
    – Daniel McLaury
    Commented Apr 15, 2014 at 7:37
  • $\begingroup$ The additive group modulo $n$. Also $\mathbb Z^*_n$ is the multiplicative group consisting of $0<a\le n$ such that $(a,n)=1$ $\endgroup$
    – Karthik C
    Commented Apr 15, 2014 at 7:38
  • $\begingroup$ What is the map $D$ ? $\endgroup$
    – Dietrich Burde
    Commented Apr 15, 2014 at 9:01
  • $\begingroup$ $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$. $\endgroup$
    – Karthik C
    Commented Apr 15, 2014 at 10:20
  • 1
    $\begingroup$ @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$. $\endgroup$
    – jpvee
    Commented Apr 15, 2014 at 13:39

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Whew! Was it that simple!? But really credit to you for making it look so easy! $\endgroup$
    – Karthik C
    Commented Apr 16, 2014 at 5:23
  • $\begingroup$ 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$! $\endgroup$
    – Karthik C
    Commented Apr 16, 2014 at 5:31
  • 1
    $\begingroup$ 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. $\endgroup$
    – Greg Martin
    Commented Apr 16, 2014 at 5:46
  • $\begingroup$ 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! $\endgroup$
    – Karthik C
    Commented Apr 16, 2014 at 5:50

You must log in to answer this question.

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