Groups Theory and Coding : Semester Exam Important

 Q. Define a group.

- A non empty set G with binary operation * is called a group if for every element c belongs to G.

The following properties hold:

1. Closure: For two elements a and b ∈ G, a*b  ∈ G.

2. Associativity : for a, b ,c ∈ G 

(a*b) *c = a* (b*c)

3. Identity : There exist e ∈ G such that a * e = e * a = a.

4. Inverse: For each a ∈ G there exists a ∈ G such that a*a-1 = a -1*a = e

Q. The relation R on Z (integers) is defined as follows: xRy if and only if 5x + 6y is divisible by 11, for x, y ∈ Z.

- 

To determine whether R is an equivalence relation, we need to verify three properties: reflexivity, symmetry, and transitivity.

Reflexivity: if 5x + 6x is divisible by 11. 

Simplifying, we have 11x, which is divisible by 11. 

Therefore, the relation is reflexive.

Symmetry: 

If 5x + 6y is divisible by 11, then we want to check if 5y + 6x is also divisible by 11. 

Rearranging the terms, we have 6x + 5y, which is the same as 5y + 6x. 

Thus, if xRy holds, then yRx holds as well. 

Therefore, the relation is symmetric.

Transitivity: 

If 5x + 6y is divisible by 11 and 5y + 6z is divisible by 11, we want to check if 5x + 6z is also divisible by 11. 

we have (5x + 6y) + (5y + 6z) = 5x + 6z + 11y. 

Since both 5x + 6y and 5y + 6z are divisible by 11, their sum is also divisible by 11. 

Therefore, xRy and yRz imply xRz, and the relation is transitive.

Since the relation R satisfies all three properties of reflexivity, symmetry, and transitivity, we can conclude that it is an equivalence relation on Z.

Q. Express the following permutation in S7 as product of disjoint cycles and hence find order of it :

Also determine whetere it is even or odd.

- Product of Disjoint cycles :

(1 3) (2 4 5) ( 6 7)

- Since it has 3 disjoint cycles it is odd.

Q. Write the composition table for (Z8, +8) and

1. find order of all elements 2. Find all subgroups 3. Is it cyclic group ? If yes, write all generators

- The set for the group (Z8, +8) consists of the integers modulo 8. Therefore, the set is:

+8	0	1	2	3	4	5	6	7
0	0	1	2	3	4	5	6	7
1	1	2	3	4	5	6	7	0
2	2	3	4	5	6	7	0	1
3	3	4	5	6	7	0	1	2
4	4	5	6	7	0	1	2	3
5	5	6	7	0	1	2	3	4
6	6	7	0	1	2	3	4	5
7	7	0	1

Z8 = {0, 1, 2, 3, 4, 5, 6, 7}

Now, let's proceed to the other questions:

1. Find the order of all elements: The order of an element in a group is the smallest positive integer n such that the element raised to the power of n gives the identity element. For the group (Z8, +8), the order of each element is as follows:

   • Order of 0: 1 (0 + 0 = 0)
   • Order of 1: 8 (1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 0)
   • Order of 2: 4 (2 + 2 + 2 + 2 = 0)
   • Order of 3: 8 (3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 = 0)
   • Order of 4: 2 (4 + 4 = 0)
   • Order of 5: 8 (5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 = 0)
   • Order of 6: 4 (6 + 6 + 6 + 6 = 0)
   • Order of 7: 8 (7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 = 0)

2. Find all subgroups: In the case of the additive group (Z8, +8), the subgroups are the sets of elements that form a group under the same operation. The subgroups of Z8 are:

   • Subgroup {0} (the trivial subgroup)
   • Subgroup {0, 4} (the subgroup of even elements)
   • Subgroup {0, 2, 4, 6} (the entire group Z8)

3. Is it a cyclic group? If yes, write all generators: A group is cyclic if there exists an element in the group such that its powers generate the entire group. In the case of (Z8, +8), it is indeed a cyclic group. The generators of the group are the elements that have an order equal to the order of the group, which is 8. The generators are:

• Generator 1: 1
• Generator 3: 3
• Generator 5: 5
• Generator 7: 7
  • Q. Find the greatest common divisor d of 4999 and 1109. Hence find integeres m and n such that d=4999m + 1109n

  1. Euclidean algorithm to find the GCD:

     • Divide 4999 by 1109: 4999 = 4 * 1109 + 103
     • Divide 1109 by 103: 1109 = 10 * 103 + 99
     • Divide 103 by 99: 103 = 1 * 99 + 4
     • Divide 99 by 4: 99 = 24 * 4 + 3
     • Divide 4 by 3: 4 = 1 * 3 + 1
     • Divide 3 by 1: 3 = 3 * 1 + 0
     • The GCD is the last non-zero remainder, which is 1.

  2. Extended Euclidean algorithm to find m and n:

     • Start with the last two equations from the Euclidean algorithm:
       • 4 = 1 * 3 + 1
       • Substitute 3 = 99 - 24 * 4 from the Euclidean algorithm: 4 = 1 * (99 - 24 * 4) + 1
       • Rearrange the equation: 4 = 1 * 99 + (-24) * 4 + 1 4 = 99 * 1 + (-24) * 4 + 1
       • Compare the coefficients to find m and n: m = 1 n = -24

  Therefore, the GCD of 4999 and 1109 is 1, and the corresponding values of m and n are m = 1 and n = -24

Q. Prove the every subgroup of cyclic group is cyclic.

- Let G be a cyclic group generated by 'a', and H be a subgroup of G.

Case 1: H is the trivial subgroup {e}:

• H contains only the identity element, which is cyclic.

Case 2: H is a non-trivial subgroup:

• Let 'b' be an element of H such that b ≠ e.
• Since G is cyclic, there exists an integer k such that b = a^k.
• Now, consider the subgroup H.
• For any element h in H, h * b = a^m * a^k = a^(m + k), where m is an integer.
• Therefore, H is generated by a^(m + k), which means H is cyclic.

Hence, every subgroup of a cyclic group is cyclic.

Q. Write all subgroups of Z10 and also write their generators.

-The group Z10, also known as the integers modulo 10 under addition, has the following subgroups:

1. The trivial subgroup: {0}. This subgroup consists only of the identity element 0 and is generated by 0.

2. The subgroup {0, 5}. This subgroup is generated by the element 5, as 5 + 5 = 10 ≡ 0 (mod 10).

3. The subgroup {0, 2, 4, 6, 8}. This subgroup is generated by the element 2, as 2 + 2 = 4 ≡ 0 (mod 10).

4. The entire group Z10: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. This subgroup is generated by any element of Z10.

Therefore, the subgroups of Z10 are: {0}, {0, 5}, {0, 2, 4, 6, 8}, and Z10 itself. The generators of these subgroups are 0, 5, 2, and any element of Z10, respectively.'

Q. Find remainder of 9^153 when divided by 11.

- To find the remainder of 9^153 when divided by 11, we can use the concept of modular arithmetic.

First, let's observe a pattern by calculating some powers of 9 modulo 11:

9^1 ≡ 9 (mod 11) 9^2 ≡ 4 (mod 11) 9^3 ≡ 3 (mod 11) 9^4 ≡ 5 (mod 11) 9^5 ≡ 1 (mod 11) 9^6 ≡ 9 (mod 11) 9^7 ≡ 4 (mod 11) ...

We notice that the remainders repeat after every 5 powers.

Now, we can find the remainder of 9^153 by dividing 153 by 5 and using the corresponding power from the pattern.

153 ÷ 5 = 30 remainder 3

Therefore, 9^153 ≡ 9^3 (mod 11).From the pattern, we know that 9^3 ≡ 3 (mod 11).Hence, the remainder of 9^153 when divided by 11 is 3.

Q. Write the addition table for (Z5, +5).

- +5 | 0 1 2 3 4 ------------------------ 0 | 0 1 2 3 4 1 | 1 2 3 4 0 2 | 2 3 4 0 1 3 | 3 4 0 1 2 4 | 4 0 1 2 3

Q. Prove that integers 361 and 420 are co primes (Relatively prime.)

-

Using the Euclidean algorithm, we can find the GCD of 361 and 420 as follows:

420 = 1 * 361 + 59 361 = 6 * 59 + 7 59 = 8 * 7 + 3 7 = 2 * 3 + 1

The last non-zero remainder obtained from the Euclidean algorithm is 1. Therefore, the GCD of 361 and 420 is 1.

Since the GCD is 1, it means that there are no common factors other than 1 between 361 and 420. Hence, 361 and 420 are coprime or relatively prime.

Q. Draw the composition table for the set G = {1,-1,i, -i} under multiplication. Find all the generators for the above group.

- x | 1 -1 i -i ----------------------- 1 | 1 -1 i -i -1 | -1 1 -i i i | i -i -1 1 -i | -i i 1 -1

From the composition table, we can see that:

• The element 1 generates the entire group since any element raised to the power of 1 is itself.
• The element -1 also generates the entire group since (-1) * (-1) = 1, and any element raised to an even power becomes 1.
• The elements i and -i generate the subgroup {i, -i}.

Therefore, the generators of the group G = {1, -1, i, -i} under multiplication are 1, -1, i, and -i.

Q. Consider the following permutations:

T= 1 2 3 4 5 6 3 4 5 6 1 2 P= 1 2 3 4 5 6 2 4 3 1 6 5 Find : (1) T. P^-1 (2) T^-1. P^2

Answer:

P^(-1) = 1 2 3 4 5 6 4 1 2 3 6 5

T . P^(-1) = 1 2 3 4 5 6 2 3 4 1 5 6

T^(-1) = 1 2 3 4 5 6 5 6 1 2 3 4

T^(-1) . P^2 = 1 2 3 4 5 6 2 3 5 6 4 1

Q.For any x ∈ G, does the inverse of x, ie x^-1 exist in G? Find the inverse of x. Justify your answer.

Since G is a group, it must satisfy the following properties:

1. Closure: For any elements a, b ∈ G, the operation between them (denoted as a * b) results in another element that is also in G.
2. Associativity: For any elements a, b, c ∈ G, (a * b) * c = a * (b * c).
3. Identity element: There exists an element e in G such that for any element a ∈ G, a * e = e * a = a.
4. Inverse element: For every element a in G, there exists an element b in G such that a * b = b * a = e, where e is the identity element of G.

Since G is a group, it follows that every element x ∈ G has an inverse x^(-1) in G. This is because the existence of an inverse is one of the defining properties of a group.

Q. Find the remainder of 333^111 when divided by 7

Let's observe a pattern by calculating some powers of 333 modulo 7:

333^1 ≡ 1 (mod 7) 333^2 ≡ 1 (mod 7) 333^3 ≡ 1 (mod 7) 333^4 ≡ 1 (mod 7)

We notice that the remainders repeat after every 3 powers.

Now, we can find the remainder of 333^111 by dividing 111 by 3 and using the corresponding power from the pattern.

111 ÷ 3 = 37 remainder 0

Therefore, 333^111 ≡ 333^0 (mod 7).

From the pattern, we know that 333^0 ≡ 1 (mod 7).

Hence, the remainder of 333^111 when divided by 7 is 1.