# Number of Elements $(\bar a, \bar b) \in (\mathbb{Z} / N \mathbb{Z})^2$ with order $N$ and $2\nmid ab$.

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

-

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