Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am searching for the number of Elements $(\bar a, \bar b) \in (\mathbb{Z} / N \mathbb{Z})^2$ with order $N$ and $2 \nmid ab$, where $N$ is an even number and $N\geq 4$.

It is known, that the number of Elements $(\bar a, \bar b) \in (\mathbb{Z} / N \mathbb{Z})^2$ with order $N$ is given by $N^2\prod\limits_{p\mid N} (1-\frac 1{p^2})$, where $p$ are prime numbers.

I suppose, that the number of Elements also fulfilling $2\nmid ab$ is given by $\frac 13 \cdot N^2\prod\limits_{p \mid N} (1-\frac 1{p^2})$.

Does anyone have an idea, how I have to count for proving this? Thanks a lot, Greyfox

share|cite|improve this question

If you have two natural numbers $a$ and $b$, their product is odd (which is the condition you look for) in $1/3$ of the possible situations: $a$ and $b$ can be both odd, one odd and one even (both even is impossible).

Edit. You can convince yourself that the proportions are of $1/3$ by visualizing your groups (all together!) $\mathbb Z/N\mathbb Z\times\mathbb Z/N\mathbb Z$ in a sort of square table where you put all the couples (all elements of the group). Start with the row $$ (0,0)\,\,\,(0,1)\,\,\,(0,2)\,\,\,(0,3). $$ Of course you should mark all those couples $(a,b)$ with $(a,b,N)=1$, in each group. (Try with $N=4$ and then pass to $N=6$...). You will notice that when you pass from $N$ to $N+2$, you add two columns and two rows to your big square, but the first row and the first column do not contain any element of the shape (odd,odd). Instead, on the "borderline" column and row you will notice that for every good couple (i.e. $(a,b)$ with $(a,b,N+2)=1$ and $a,b$ both odd) there are exactly two bad couples: one above and one on its left. All this can be suitably formalized...

share|cite|improve this answer
That is correct. And since N is even, the case that a and b are both even can not exists, since the order of $(\bar a,\bar b)$ is N, iff $gcd(a,b,N)=1$. So I only have the three cases: 1)a,b odd; 2) a even, b odd; 3) a odd, b even. That's how I came to the factor $\frac 13$ . But how can I make sure that any of this cases appears exactly as often as the others? – Greyfox Mar 1 '13 at 21:37
You are right. I edited my answer. – Brenin Mar 2 '13 at 11:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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