Results 1 to 4 of 4

Thread: Group of Units (Abelian)

  1. #1
    Member
    Joined
    Mar 2008
    Posts
    99

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    I assumed that $\displaystyle U_n $ is the group of all invertible congruence classes modulo $\displaystyle n$ under multiplication.

    Quote Originally Posted by shadow_2145 View Post
    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$.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by shadow_2145 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by shadow_2145 View Post
    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$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Group of Units
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: Jan 20th 2011, 05:02 AM
  2. Group of units
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: Nov 1st 2010, 01:05 AM
  3. Replies: 3
    Last Post: Apr 21st 2010, 03:53 PM
  4. Is the subgroup of an abelian group always abelian?
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: Dec 6th 2009, 11:38 PM
  5. Group of Units
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 16th 2009, 12:47 PM

Search Tags


/mathhelpforum @mathhelpforum