# Math Help - Group of Units (Abelian)

1. ## Group of Units (Abelian)

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

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

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

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

(b) Compute $|\{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 $U_n$ is the group of all invertible congruence classes modulo $n$ under multiplication.

1) Find an element of maximal order in $U_{884}$.
Note that $884 = 4\cdot 13\cdot 17$.
Thus, $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 $([1]_2,[1]_{12},[1]_{16})$ has maximum order with $\text{lcm}(2,12,16)=48$.

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

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

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

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

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

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

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

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

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

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