Question

Find a complete set of incongruent primitive roots of \(13 .\)

Short answer

A complete set of incongruent primitive roots of 13 is {2, 6}.

Step-by-step solution

Calculate Euler's totient function

Find the value of \(\phi(13)\). Since 13 is a prime number, by definition, \(\phi(13) = 13-1 = 12\). Therefore, there are 12 integers less than 13 that are coprime to 13.

Calculate primitive roots count

To find the number of primitive roots of 13, we need to find the value of \(\phi(\phi(13))\). We have \(\phi(13) = 12\). Now we need to calculate \(\phi(12)\). The prime factors of 12 are 2 and 3. Thus, Euler's totient function for 12 is \(\phi(12) = 12(1 - \frac{1}{2})(1 - \frac{1}{3}) = 12 \times \frac{1}{2} \times \frac{2}{3} = 4\). So, there are 4 primitive roots of 13.

Check the possible primitive roots

Now we need to check for possible primitive roots of 13. Since there are 4 primitive roots, we will check the powers of each potential primitive root, modulo 13. Recall that the powers we need to check are 1, 2,...,11.

Finding the primitive roots

Let's check the powers of each potential primitive root, modulo 13: 2: \(2^1 \equiv 2 \bmod{13}, 2^2 \equiv 4\bmod{13},2^3 \equiv 8\bmod{13},2^4\equiv3\bmod{13},2^5\equiv 6\bmod{13}, 2^6 \equiv 12 \bmod{13}, 2^7\equiv11\bmod{13},2^8\equiv9\bmod{13},2^9\equiv5\bmod{13},2^{10}\equiv10\bmod{13},2^{11}\equiv 7 \bmod{13}\). So, 2 is a primitive root of 13. Now let's check for other primitive roots: 3: \(3^1 \equiv 3\bmod{13},3^2 \equiv 9\bmod{13},3^3 \equiv 1\bmod{13}\). 3 is not a primitive root of 13 because it repeats after only three powers. Continue checking for other primitive roots: 6: \(6^1 \equiv 6\bmod{13},6^2 \equiv 10\bmod{13},6^3 \equiv 8\bmod{13},6^4 \equiv 9\bmod{13}, 6^5 \equiv 2\bmod{13},6^6 \equiv 12 \bmod{13},6^7 \equiv 7\bmod{13}, 6^8 \equiv 3\bmod{13}, 6^9 \equiv 5\bmod{13}, 6^{10}\equiv 4 \bmod{13}, 6^{11} \equiv 11 \bmod{13}\). So, 6 is a primitive root of 13. 7: \(7^1 \equiv 7\bmod{13},7^2 \equiv 10\bmod{13},7^3 \equiv 5\bmod{13},7^4 \equiv 9\bmod{13},7^5 \equiv 8\bmod{13},7^6 \equiv 12 \bmod{13},7^7 \equiv 11\bmod{13}, 7^8 \equiv 6\bmod{13}, 7^9 \equiv 3\bmod{13}, 7^{10}\equiv 1 \bmod{13}\). So, 7 is not a primitive root of 13. 11: \(11^1 \equiv 11 \bmod{13}, 11^2 \equiv 4 \bmod{13}, 11^3 \equiv 5 \bmod{13}, 11^4 \equiv 3 \bmod{13}, 11^5 \equiv 7 \bmod{13}, 11^6 \equiv 12 \bmod{13}, 11^7 \equiv 6 \bmod{13}, 11^8 \equiv 9 \bmod{13}, 11^9 \equiv 8 \bmod{13}, 11^{10} \equiv 1 \bmod{13}\). So, 11 is not a primitive root of 13.

Present the final set of incongruent primitive roots

After checking all potential primitive roots, we have found that there are two primitive roots: \(2\) and \(6\). Therefore, a complete set of incongruent primitive roots of 13 is \(\{2, 6\}\).

Key concepts

Euler's Totient Function

Euler's totient function, often denoted as \( \phi(n) \), is a key concept in number theory. It represents the number of integers up to \( n \) that are coprime to \( n \), meaning they share no common factors other than the number one. The totient function is essential for understanding the distribution of primitive roots and solving equations in modular arithmetic.

To calculate \( \phi(n) \), especially when \( n \) is a prime number, it simplifies to \( n - 1 \). This is because all numbers less than a prime are automatically coprime to it. For composite numbers, we use the prime factorization and apply the formula:
\[ \phi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right) \]
where \( p_1, p_2, \ldots, p_k \) are the distinct prime factors of \( n \).

This function is particularly handy in cryptography for calculating possibilities and in problems concerning primitive roots, like identifying those of a given integer such as 13.

Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after reaching a certain value, known as the modulus. It's akin to how our clock works: after 12 hours, the clock returns to 1.

When we work modulo \( n \), we focus on the remainder of division by \( n \). For instance, \( 14 \equiv 2 \pmod{12} \), because when we divide 14 by 12, the remainder is 2. This field of arithmetic is crucial for simplifying problems in number theory, particularly those involving periodic processes or cycles.

Modular arithmetic is foundational in finding primitive roots. A primitive root of a prime \( p \) is an integer \( g \) such that every number coprime to \( p \) is a power of \( g \) mod \( p \). In essence, \( g \) is capable of generating all numbers from 1 to \( p-1 \) upon exponentiation. This process can assure the presence of periodic properties used in cryptographical algorithms.

Incongruent Integers

Incongruent integers make up a concept in modular arithmetic where two numbers are said to be incongruent modulo \( n \) if they have different remainders when divided by \( n \).

For example, under modulus 5, the integers 7 and 12 are congruent because both leave a remainder of 2 when divided by 5, expressed as \( 7 \equiv 2 \equiv 12 \pmod{5} \). In contrast, 7 and 3 are incongruent as they leave different remainders (2 and 3, respectively) under the same modulus.

This concept is crucial in identifying sets of numbers with no overlap in residue classes for a given modulus, such as when determining a complete set of primitive roots. A complete set of primitive roots of a prime modulus are incongruent to each other, ensuring they span a full cycle when exponentiated up to \( p-1 \). This helps in securely structuring algorithms where randomness and non-repetition are key components, such as in cryptographic systems.