EE720: Problems set 2.
1: CRT, cyclic groups, finite fields
Sept 6, 2020
1. Find q-adic expansions: of 34787, 55833, (34787)(55833) for q = 25, 101 on calculator.
2. Show how you can find the multiple base expansion of numbers. (We can call such
expansion polyadic). For b1 = 2, b2 = 3 such an expansion represents a number a in the
form
a = a00 + a10 2 + a01 3 + a11 2.3 + a21 22 .3 + a12 2.32 + a22 22 .32 + . . .
What is the largest power of the base required given the number a? Develop a method
of high school multiplication and division with remainder in terms of polyadic expansion.
Compute expansions of numbers in problem 1 above in bases 2, 3.
3. Compute gcd(139024789, 93278890) using calculator and find one extended Euclidean
representation of the gcd.
4. Let d be gcd(a, b) and u, v satisfy d = au + bv. Find all solutions x, y of the identity
d = ax + by in terms of a, b, u, v, d.
5. For a natural number n and a prime p, order of p in n denoted ord p (n) is the power of p
that appears in prime factorization of n. Find ord 2 (2816), ord 7 (2222574487), ord p (46375)
for p = 3, 5, 7.
6. Order of an element in a group. For groups Z∗n this is the multiplicative order. Use the
algorithm discussed in class to find orders of at one of the primes not dividing φ(n) in Z∗n
for n = 256, 1000, 2816. Then check your answer using the sage function for multiplicative
order.
7. Find at least one primitive element modulo p = 23, 29, 41, 43. Find all primitive roots of
p = 11, 17, 23. How many primitive roots modulo p are there for a prime p? Compute
number of primitive roots of p = 41, 57, 97, 101, 1001. How many primitive roots are there
in Z∗n for n = 23 ∗ 29.
8. Let Cn denote a cyclic group of order n. Write the lattice of all subgroups of C100 , C36 ,
C12 .
9. Solve following congruences (or explain why solutions dont exist) using Euler’s theorem
(i.e. not using extended Euclidean algorithm).
(a) x = 37 mod 43, x = 22 mod 49, x = 18 mod 71.
1
(b) x = 133 mod 451, x = 237 mod 697.
(c) x = 5 mod 9, x = 6 mod 10, x = 7 mod 11.
10. Find following powers by fast exponentiation using binary expansion and also using CRT
whenever possible 1) 17183 mod 256, 2) 2477 mod 1000, 11507 mod 1237.
11. Construct irreducible polynomials of degree 2, 3, 5, over GF (p) for p = 2, 3, 5, 7, 11. Con-
struct extension fields Fq for q = pn for p = 2, 3, n = 2 and write their multiplication table
in terms of a root θ of the chosen irreducible polynomial. Find one primitive element of
Fq for these fields.
12. Write the lattice diagram of all subfields of F216 , F38 . Write the lattice diagram of all
subgroups of the cyclic group of units of these fields. Are these same? Justify.
13. Find primitive elements of the fields F24 , F33 by representing them in a polynomial basis
of root of an irreducible polynomial.
14. Represent finite fields F2m for m = 3, 5, 7 by a polynomial basis {1, θ, . . . , θm−1 }. Find
order of θ in each of these fields. Show that the polynomial X 8 + X 4 + X 3 + X + 1 is
irreducible over F2 . Find order of a root of this polynomial. Is this polynomial primitive?