Question

Let \(p, q \in \mathbb{N}\) be distinct odd primes, \(n=p q\), and \(k, l \in \mathbb{N}\). (i) Given a primitive \(k\) th root of unity in \(\mathbb{Z}_{p}^{\times}\)and a primitive lth root of unity in \(\mathbb{Z}_{q}^{\times}\), how can you construct a primitive \(m\) th root of unity in \(\mathbb{Z}_{n}^{\times}\), where \(m=\operatorname{lcm}(k, l)\) ? (ii) Show that \(\mathbb{Z}_{n}^{\times}\)contains a primitive \(k\) th root of unity if and only if \(k \mid \operatorname{lcm}(p-1, q-1)\). (iii) Find primitive 16 th roots of unity in \(\mathbb{Z}_{17}^{\times}\)and in \(\mathbb{Z}_{97}^{\times}\), and construct a primitive 16 th root of unity in \(\mathbb{Z}_{1649}^{\times}\).

Short answer

Find primitive roots modulo each prime, combine using the CRT, ensuring divisibility of 16 in \(\mathbb{Z}_{1649}^{\times}\).

Step-by-step solution

Evaluate Primitive Roots in Modulo Terms

Select primitive roots for odd primes \(p\) and \(q\). For instance, let \(a\) be a primitive \(k\)-th root of unity in \(\mathbb{Z}_p^{\times}\), and \(b\) be a primitive \(l\)-th root of unity in \(\mathbb{Z}_q^{\times}\). These roots exist under the condition that \(a^k \equiv 1 \pmod{p}\) and \(b^l \equiv 1 \pmod{q}\).

Define Least Common Multiple

Determine \(m = \operatorname{lcm}(k, l)\). We need to ascertain the primitive root of order \(m\) or \(\operatorname{lcm}(k, l)\).

Construct the Primitive m-th Root in \(\mathbb{Z}_n^{\times}\)

Use the Chinese Remainder Theorem to combine these roots into \(\mathbb{Z}_n^{\times}\). Essentially, find an element \(z \in \mathbb{Z}_n^{\times}\) such that: \[(z \equiv a \pmod{p})\] \[(z \equiv b \pmod{q})\] This exploits congruence properties to ensure \(z\) is a primitive \(m\)-th root of unity in \(\mathbb{Z}_n^{\times}\).

Identify Conditions for Primitive k-th Root

To demonstrate \(\mathbb{Z}_n^{\times}\) contains a primitive \(k\)-th root of unity, note that such a root exists if the order divides \(\operatorname{lcm}(p-1, q-1)\). Specifically, check if \(k \mid \operatorname{lcm}(p - 1, q - 1)\), which confirms a primitive \(k\)-th root can exist in \(\mathbb{Z}_n^{\times}\).

Compute Primitive 16th Roots in \(\mathbb{Z}_{p}^{\times}\) and \(\mathbb{Z}_{q}^{\times}\)

First, check if 16 divides \(p-1\) for 17 and \(q-1\) for 97.- For \(p = 17\), \(16 \mid 16\); any primitive element of \(\mathbb{Z}_{17}^{\times}\) can be used.- For \(q = 97\), \(16 \mid 96\); also use a primitive element here.Select a primitive element (generator) of each of \(\mathbb{Z}_{17}^{\times}\) and \(\mathbb{Z}_{97}^{\times}\) such that \(g^{16} \equiv 1 \pmod{n}\).

Combine to Form a Primitive 16th Root in \(\mathbb{Z}_{1649}^{\times}\)

Now let's find and combine the calculated roots of unity with respect to modulo \(n = 1649\), using the steps above:- Use Chinese Remainder Theorem to synchronize modular conditions for \(p\) and \(q\):\[(z \equiv g_1 \pmod{17})\] \[(z \equiv g_2 \pmod{97})\] The synthesis of these solutions yields a primitive \(16\)-th root in \(\mathbb{Z}_{1649}^{\times}\).

Conclusion and Verification

Verify the primitive roots so found satisfy the order criteria under the modulo operations described. Ultimately, we ensure the derived root complies with the expected order across both moduli and yields a coherent primitive root within \(\mathbb{Z}_{1649}^{\times}\).

Key concepts

Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) is a gem in number theory that allows you to work with congruence equations. Imagine you have different congruences like finding numbers that satisfy specific remainders when divided by different primes. CRT provides a systematic way to find such a number that satisfies all these conditions simultaneously. In simpler terms, it aligns several calculations done in different "modules" or "realities" into one unified result.

Typically, when you have two coprime integers, say, primes like 17 and 97, the CRT can help construct a solution to a system of modular equations. For instance, if you have an equation that needs to satisfy certain conditions mod 17 and mod 97, the CRT helps you find that single congruence that fulfills both.

• You're given: equations of the form, say, \( z \equiv a \pmod{p} \) and \( z \equiv b \pmod{q} \).
• The CRT assures a unique solution modulo the product of these primes e.g., 17 * 97 = 1649.
• This solution will be the same modulo each of the prime factors simplifying your task of solving congruences.

This way, CRT becomes particularly handy when constructing a primitive root in combined modular systems like \( \mathbb{Z}_{n}^{\times} \). This allows you to blend primitive roots from smaller primes into one cohesive solution for larger prime products.

Modular Arithmetic

In mathematics, modular arithmetic is often referred to as "clock arithmetic." It revolves around integers and the idea of wrapping numbers around a given modulus. Think of a clock: once it passes 12, it wraps back around to 1. In the same way, in modular arithmetic, numbers wrap around a specified value called the modulus.

For example, if you have a modulus of 5, then numbers would wrap every five counts: 0, 1, 2, 3, 4, then return to 0. This is referred to as reducing numbers mod 5.

• An operation in modular arithmetic could be written as: \( a \equiv b \pmod{n} \). This means when \( a \) is divided by \( n \), it leaves the same remainder as \( b \).
• Key operations - addition, subtraction, and multiplication – all have counterparts in modular arithmetic. It is fascinating but straightforward: \( (a+b) \bmod n \), \( (a-b) \bmod n \), and \( (a*b) \bmod n \).
• This way of handling numbers is crucial in defining and understanding the structure of sets like \( \mathbb{Z}_n \), which denotes integers 0 through \( n-1 \).

Modular arithmetic forms the basis for many cryptographic systems, hash functions, and even the calculations you're doing to find roots of unity. Understanding it ensures a deep, fundamental comprehension of division and remainder concepts utilized in many mathematical applications.

Least Common Multiple

The Least Common Multiple (LCM) of two integers is the smallest number that is a multiple of both. It is extremely useful in many areas of math, for instance, when adding fractions with different denominators or when solving congruences involving multiple modulus operations. Finding the LCM is crucial for ensuring you have the order necessary for certain mathematical operations.

When dealing with primitive roots, the LCM helps determine the order that a new combined root should have. For example:

• To find an LCM of two numbers \( k \) and \( l \), you can use the formula: \[ \operatorname{lcm}(k, l) = \frac{|k \times l|}{\gcd(k, l)} \]
• The LCM considers the highest power of all prime factors involved, ensuring you have a complete cumulative list of factors too.
• Using the LCM in modular arithmetic ensures that constructs like primitive roots align in their lowest possible shared cycle, essential when combining roots from different moduli.

Thus, when you're tasked to generate a root of a certain order, using the LCM guarantees that this root effectively combines the orders of component roots, ensuring it fits coherently in systems like \( \mathbb{Z}_n^{\times} \). The LCM guarantees that roots maintain the new required order, optimizing them for use within the system combining modular components.