Scribd Logo
Upload

Welcome to Scribd!

  • 4 views

    Slides Chapter 03

    Uploaded by

    akyadav123

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd

    Slides Chapter 03

    Uploaded by

    akyadav123
    4 views11 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    4 views11 pages

    Slides Chapter 03

    Uploaded by

    akyadav123

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    You are on page 1of 11

    Useful Algebraic Strucures

    Groups:
    A group is a pair <G, *>, where G is a Set & * is binary
    operation such that following properties hold,
    1.Closure: If a and b are elements of G, then so is a*b
    2.Associativity: If a, b and c are elements of G, then
    a*(b*c) = (a*b)*c
    3. Identity element: There exist an element I in G such that for all b
    in G,
    I*b=I=b*I
    4. Inverse: For each element b in G, there exists exactly one element
    c in G, such that
    b*c=c*b=I
    Examples
    • A group may be infinite such as –set of all
    integers with regular addition
    OR
    • Finite such as: Zn = {0,1,2,…,n-1} with
    modulo-n operation denoted by +n,
    Example: “<Zn-{0}, *n> is a Group only if n is a
    prime number”
    • Here, *n denote “multiplication modulo n”
    • Here, Closure & Associativity properties holds.
    Identity element is 0.
    But, does each element have inverse?
    • If n is prime, then by corollary-1, for any b in
    Zn we can find integers c & d such that,
    b*c+n*d=1
    So, n * d = 1 mod n,
    Hence b-1 = c mod n
    • If n is non-prime, let f be one of its non-zero
    factors. Suppose f has an inverse say h.
    So, f * h = 1 mod n or
    f * h = 1 + k * n (for some integer k)
    • Now, dividing throughout by n, we end up with
    equating a fraction to an integer- a contradiction.
    • Hence, some elements in Zn have no inverses.
    So, <Zn-{0}, *n> is not a group if n is non-prime.
    Hence, we conclude that “<Zn-{0}, *n> is a Group
    only if n is a prime number”.
    Notation:
    • Let, Zn* denote {i | 0<i<n and gcd(i,n)=1}
    i.e. Zn* is set of all integers modulo n that are
    relatively prime to n.

    Ex: Z5* = {1, 2, 3, 4} and Z6* = {1, 5}


    • Order of a group <G, *>: is number of elements in G.
    • Euler Totient Function: denoted by Φ(n) is the order of
    <Zn*, *n>.
    Hence, Φ(5) = 4, Φ(6) = 2
    • Sub-group: <G’, *> is a sub-group of <G, *>, if it satisfies
    all the listed properties & if G’ is subset of G.
    • Ex: Consider Z5* = {1, 2, 3, 4}
    The different sub-groups are
    < {1},*5>, <{1,4}, *5> and < Z5* ,*5>

    • Lagrange’s Theorem:
    “The order of any sub-group of a group divides
    the order of the parent group”
    • It says that, there is a restriction on the number
    of elements in sub-groups.
    • Hence, in above example, we don’t have a sub-
    group of order=3.
    • Let <G’, *> be a finite group and let g be an element
    of G.
    • We use gi to denote the element obtained by
    performing * operation on g i-times.
    ie. g * g * g * g ….*g i-times
    Hence, g
    g2 = g * g
    g3 = g * g * g
    g4 = g * g * g * g
    ...
    The list will start repeating at some point.
    • Let S denote the set of all unique elements in above
    list, then we note the following:
    • <S, *> is a subgroup of <G, *> generated by g &
    denoted it as <g>.
    • Generator:
    A group <G, *> is cyclic, if there is atleast
    one element g in it such that <g> is <G, *>. We
    refer to such an element as Generator of <G, *>.

    Ex: Consider <Z*13, *13>. In this group,


    21 mod 13 = 2 22 mod 13 = 4 23 mod 13 = 8
    24 mod 13 = 3 25 mod 13 = 6 26 mod 13 = 12
    27 mod 13 = 11 28 mod 13 = 9 29 mod 13 = 5
    210 mod 13 = 10 211 mod 13 = 7 212 mod 13 = 1

    Hence, 2 is a generator of <Z*13, *13>. But, 3 is not.


    • FACT: The group <Z*p, *p> where p is prime, is cyclic.

    • FACT: The number of generators in <Z*p, *p> is Φ(p-1).

    • FACT:
    Let p be prime and let p1,p2,……,pk be the distinct prime
    factors of p-1.
    Then, g is a generator of <Z*p, *p> if and only if
    g(p-1)/pi ≠ 1 mod p for all pi, 1≤i≤k
    Ex: Check whether 7 and 3 are generators of <Z*13, *13> ?
    The distinct prime factors of 12 are 2 and 3.
    So, p1 = 2 and p2 = 3
    Let us check whether 7 is a generator <Z*13, *13>,
    712/2 mod 13 = 76 mod 13 = -1
    and 712/3 mod 13 = 74 mod 13 = 9
    Hence, 7 passes the test and is a generator.

    But, 312/2 mod 13 = 36 mod 13 = 1


    Hence, 3 fails the test and is not a generator of <Z*13, *13>.
    Rings

    You might also like