Results 1 to 5 of 5

Math Help - number theory and abstract algebra

  1. #1
    Newbie
    Joined
    Mar 2008
    Posts
    13

    number theory and abstract algebra

    Just hoping for some help with my practice exam. Any help on any of the questions would be greatly appreciated as my lecturer is absolutely shocking. Cheers.

    (2)b

    Let n ∈ N and let p be a prime. Show that if p | n then φ(np) = pφ(n).
    Hint: consider the prime factorisation of n.

    (17)
    Show that the inverse of 5 modulo 101 is 5^99.
    Use repeated squaring to simplify 5^99 (mod101)
    Hence solve the equation 5x = 31(mod101)

    (31)
    Let P(R) be the set of all subsets of R; that is, P(R) = {X | X ⊆ R}. Let F be the set of all functions R → R. Define R : F → P(R) by R(f ) = {x ∈ R | f (x) = 0}. Prove
    that R is surjective but not injective.

    (36)b

    In which of the following is (G, ∗) a semigroup? In which is it a group? Prove your answers.

    G = N, a ∗ b = max{a, b}.
    G = R \ { 1/2 }, a ∗ b = a − 2ab + b.

    I know this is a lot of question but I'm really struggling and my test book doesn't have any examples. Thank you for all your time.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    (2) b

    \phi(n)=n\cdot{\prod_{p|n}{\left(1-\frac{1}{p}\right)}} (by p I mean prime)

    Let q be a prime such that q|n

    then: \phi(n)=n\cdot{\prod_{p|n}{\left(1-\frac{1}{p}\right)}}

    Where \prod_{p|n}{\left(1-\frac{1}{p}\right)} includes the factor \left(1-\frac{1}{q}\right) just once (1)

    So \phi(q\cdot{n})=q\cdot{n}\cdot{\prod_{p|(qn)}{\lef  t(1-\frac{1}{p}\right)}}

    But, by (1) it must be \prod_{p|(qn)}{\left(1-\frac{1}{p}\right)}=\prod_{p|n}{\left(1-\frac{1}{p}\right)} since q is already there and there are no new primes

    Therefore: \phi(q\cdot{n})=q\cdot{\phi(n)}

    (17) It follows by Fermat's Little Theorem that, since 101 is prime, a^{100}\equiv{1}(\bmod.101) where (a,101)=1

    Thus 5^{100}\equiv{1}(\bmod.101)

    We have 5\cdot{x}\equiv{31}(\bmod.101)

    Multiply both sides by 5^{99}

    So: x\equiv{3\cdot{5^{99}}}(\bmod.101)

    Now try to simplify this
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor kalagota's Avatar
    Joined
    Oct 2007
    From
    Taguig City, Philippines
    Posts
    1,026
    Quote Originally Posted by asw-88 View Post
    ...

    (36)b

    In which of the following is (G, ∗) a semigroup? In which is it a group? Prove your answers.

    G = N, a ∗ b = max{a, b}.
    G = R \ { 1/2 }, a ∗ b = a − 2ab + b.

    I know this is a lot of question but I'm really struggling and my test book doesn't have any examples. Thank you for all your time.
    this is just a direct application of the definition of a semigroup and a group.
    which takes the role of the identity? is * associative? does every element of G has an inverse? you can do it!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor kalagota's Avatar
    Joined
    Oct 2007
    From
    Taguig City, Philippines
    Posts
    1,026
    Quote Originally Posted by asw-88 View Post
    Just hoping for some help with my practice exam. Any help on any of the questions would be greatly appreciated as my lecturer is absolutely shocking. Cheers.

    (2)b

    Let n ∈ N and let p be a prime. Show that if p | n then φ(np) = pφ(n).
    Hint: consider the prime factorisation of n.
    this is my approach..

    let p be a prime such that p|n
    let the factorization of n be denoted by

    n = p^e p_1^{e_1} p_2^{e_2}... p_k^{e_k}

    where {e_i}'s are powers of the primes {p_i}'s (and of course, p is included in the factorization since p|n and e is the power of p since it is arbitrary..)

    so, np = p^{e+1} p_1^{e_1} p_2^{e_2}... p_k^{e_k}

    now, we have \varphi (n) = \varphi (p^e p_1^{e_1} p_2^{e_2}... p_k^{e_k}) = (p^{e-1})(p-1)\prod_{i=1}^k (p_i^{e_i-1})(p_i-1)

    so, \varphi (np) = \varphi (p^{e+1} p_1^{e_1} p_2^{e_2}... p_k^{e_k}) = (p^e)(p-1)\prod_{i=1}^k (p_i^{e_i-1})(p_i-1)

    = (p)(p^{e-1})(p-1)\prod_{i=1}^k (p_i^{e_i-1})(p_i-1) = p \, \varphi (n). QED..
    Last edited by kalagota; April 9th 2008 at 07:28 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,641
    Thanks
    1592
    Awards
    1
    Quote Originally Posted by asw-88 View Post
    (31)
    Let P(R) be the set of all subsets of R; that is, P(R) = {X | X ⊆ R}. Let F be the set of all functions R → R. Define R : F → P(R) by R(f ) = {x ∈ R | f (x) = 0}. Prove
    that R is surjective but not injective.
    Clearly the function is not injective. s(x) = x^2 \,\& \,i(x) = x then F(i) = F(s)=\{0\}.

    The surjectivity is the hard part. Do you know about the characteristic function?
    \left( {\forall A \in P(\mathbb{R})} \right)\left[ {\chi _A :\mathbb{R} \to \mathbb{R}} \right] defined by \chi _A (x) = \left\{ {\begin{array}{ll}<br />
   {1,} & {x \in A}  \\   {0,} & {x \notin A}  \\ \end{array} } \right.
    If M \in P(\mathbb{R}) we must find a function h:\mathbb{R} \to \mathbb{R}\,\& \,F(h) = M.
    Let N = \mathbb{R}\backslash M, that is the complement of M in \mathbb{R}.
    Now the claim is that \chi _N is such a function.
    Can you prove that?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Algebra help in Hardy's 'Intro to Number Theory'
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: July 5th 2010, 05:39 PM
  2. Set Theory Abstract Algebra
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 23rd 2010, 03:19 PM
  3. Replies: 0
    Last Post: April 23rd 2010, 11:37 PM
  4. group theory abstract algebra
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: October 26th 2009, 04:54 PM
  5. Algebra - Number Theory
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 2nd 2009, 01:51 AM

Search Tags


/mathhelpforum @mathhelpforum