# Thread: Group of Units (Abelian)

1. ## Group of Units (Abelian)

I am in dire need of help! $\displaystyle U_n$ is an abelian group under multiplication mod $\displaystyle (n)$. If you need more information, please let me know.

1) Find an element of maximal order in $\displaystyle U_{884}$.

2) Let $\displaystyle a$ and $\displaystyle e$ be integers with $\displaystyle e \geq4$ and $\displaystyle |[a]_{16}|=4$. Prove that $\displaystyle |[a]_{2^e}|= 2^{e-2}$

3) Let $\displaystyle e$ and $\displaystyle f$ be positive integers.
(a) Determine the number of elements of order $\displaystyle 2^f$ in $\displaystyle U_{2^e}$.

(b) Compute $\displaystyle |\{a^{2^f} | a\in U_{2^e}\}|$

Thanks for any and all help! I need help with these by tomorrow night, thanks

2. I assumed that $\displaystyle U_n$ is the group of all invertible congruence classes modulo $\displaystyle n$ under multiplication.

1) Find an element of maximal order in $\displaystyle U_{884}$.
Note that $\displaystyle 884 = 4\cdot 13\cdot 17$.
Thus, $\displaystyle U(\mathbb{Z}_{884})\simeq U(\mathbb{Z}_4)\times U(\mathbb{Z}_{13})\times U(\mathbb{Z}_{17})\simeq \mathbb{Z}_2\times \mathbb{Z}_{12}\times \mathbb{Z}_{16}$.
The element $\displaystyle ([1]_2,[1]_{12},[1]_{16})$ has maximum order with $\displaystyle \text{lcm}(2,12,16)=48$.

2) Let $\displaystyle a$ and $\displaystyle e$ be integers with $\displaystyle e \geq4$ and $\displaystyle |[a]_{16}|=4$. Prove that $\displaystyle |[a]_{2^e}|= 2^{e-2}$
$\displaystyle |[a]_{16}| = 4$ means $\displaystyle a^4 \equiv 1(\bmod 16)$, another way to write this is as $\displaystyle a^{2^2} \equiv 1(\bmod 2^4)$.
We need to prove that $\displaystyle a^{2^{e-2}}\equiv 1(\bmod 2^e)$ we do this by induction.
If $\displaystyle e=4$ there is nothing to prove because that is already given to us.
Assume that $\displaystyle a^{2^{k-2}} \equiv 1(\bmod 2^k)$ holds for $\displaystyle k\geq 4$.
Then, $\displaystyle \left( a^{2^{k-2}} \right)^2 \equiv 1(\bmod 2^{k+1})$ thus, $\displaystyle a^{2^{k-1}} \equiv 1(\bmod 2^{k+1})$ completing induction.

Note: We use the fact that if $\displaystyle a\equiv b(\bmod p^n)$ then $\displaystyle a^p \equiv b^p (\bmod p^{n+1})$ where $\displaystyle p$ is a prime.

3) Let $\displaystyle e$ and $\displaystyle f$ be positive integers.
(a) Determine the number of elements of order $\displaystyle 2^f$ in $\displaystyle U_{2^e}$.
Remember a simple fact about cyclic groups. Let $\displaystyle m\geq 2$ and $\displaystyle [k]_m \in \mathbb{Z}_m$ then the order of $\displaystyle [k]_m = m/\gcd(k,m)$.

Say that $\displaystyle e\geq 3$ (when $\displaystyle e=1,2$ you can do yourself). Then it is known that $\displaystyle U(\mathbb{Z}_{2^e}) \simeq \mathbb{Z}_{2^{e-2}}\times \mathbb{Z}_{2}$.
Any element in $\displaystyle \mathbb{Z}_{2^{e-2}}\times \mathbb{Z}_2$ has form either: $\displaystyle ([a]_{2^{e-2}},[0]_2)$ or $\displaystyle ([a]_{2^{e-2}},[1]_2)$.
The order of $\displaystyle ([a]_{2^{e-2}},[0]_2)$ is simply the order of $\displaystyle [a]_{2^{e-2}}$ in $\displaystyle \mathbb{Z}_{2^{e-2}}$.
The order of $\displaystyle ([a]_{2^{e-2}},[1]_2)$ is simply the order of $\displaystyle [a]_{2^{e-2}}$ if $\displaystyle [a]\not = [0]$, otherwise the order is $\displaystyle 2$.

You are trying to find how many elements have order $\displaystyle 2^f$. Well, if $\displaystyle f=0$ then only $\displaystyle ([0]_{2^{e-2}},[0]_2)$ has order $\displaystyle 2^0 =1$.
If $\displaystyle f=1$ then $\displaystyle ([0]_{2^{e-3}},[1]_2)$ has order $\displaystyle 2^1=2$ and all $\displaystyle 1\leq a < 2^{e-2}$ so that $\displaystyle \gcd(a,2^{e-2}) = 2^{e-3}$ have order $\displaystyle 2$.
The only such $\displaystyle a$ which makes this true is $\displaystyle a=2^{e-3}$. Thus for $\displaystyle f=1$ there are two elements with order $\displaystyle 2^1$.

Now we will consider what happens when $\displaystyle f\geq 2$.
The elements $\displaystyle ([a]_{2^{e-3}},[0]_2)$ and $\displaystyle ([a]_{2^{e-3}},[1]_2)$ so that $\displaystyle \gcd( a,2^{e-2}) = 2^{e-f-2}$ with $\displaystyle 1\leq a < 2^{e-2}$ are precisely that have this order.

It remains to count the # of $\displaystyle 1\leq a < 2^{e-2}$ so that $\displaystyle \gcd(a,2^{e-2})=2^{e-f-2}$.
Note $\displaystyle 2^{e-f-2}|a$ thus $\displaystyle a=2^{e-f-2}b$ where $\displaystyle 1\leq b< 2^f$ because we need $\displaystyle 1\leq a < 2^{e-f-2}$.
Thus, $\displaystyle \gcd(2^{e-f-2}b,2^{e-2}) = 2^{e-f-2}\implies \gcd(b,2^f) = 1$ where $\displaystyle 1\leq b < 2^f$.
There are of course $\displaystyle \phi (2^f) = 2^{f-1}$ such numbers.

Finally we need to double this number because that is the number for each case: $\displaystyle ([a]_{2^{e-2}},[0]_2),([a]_{2^{e-2}},[1]_2)$.
We get that the number of elements of order $\displaystyle 2^f$ is equal to $\displaystyle 2\cdot 2^{f-1} = 2^f$.

As a check note that when $\displaystyle f=0$ we should have $\displaystyle 2^0 =1$ element of order $\displaystyle 1$.
Also when $\displaystyle f=1$ we should have $\displaystyle 2^1=2$ elements of order $\displaystyle 2$ (as we got above).
Thus, eventhough this formula was derived for $\displaystyle f\geq 2$ it works for $\displaystyle f\geq 0$ as well.

We conclude that there are $\displaystyle 2^f$ elements of order $\displaystyle 2^f$.