Group of Units (Abelian)

**shadow_2145** · April 30th 2008, 11:08 AM

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

**ThePerfectHacker** · April 30th 2008, 07:03 PM

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

Originally Posted by shadow_2145

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

**ThePerfectHacker** · April 30th 2008, 07:15 PM

Originally Posted by shadow_2145

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.

**ThePerfectHacker** · April 30th 2008, 08:11 PM

Originally Posted by shadow_2145

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

Thread: Group of Units (Abelian)

LinkBack

Thread Tools

Display

Group of Units (Abelian)

Similar Math Help Forum Discussions

Group of Units

Group of units

Does the group U(12) of units in Z/12 have the same structure as U(8)?

Is the subgroup of an abelian group always abelian?

Group of Units

Search Tags