Find the numbers n from the given choices with the property that 13 is a primitive root modulo n.

1)47

2)49

3)53

4)59

5)61

6)67

To determine which numbers \( n \) from the given choices have 13 as a primitive root modulo \( n \), we need to check the following conditions:

1. \( n \) should be a prime number.
2. The order of 13 modulo \( n \) should be \( n-1 \). This means that 13 raised to all powers from 1 to \( n-2 \) should not be congruent to 1 modulo \( n \), and \( 13^{n-1} \) should be congruent to 1 modulo \( n \).

Let's analyze each choice:

### 1) \( n = 47 \)
- \( n-1 = 46 \)
- Check if the order of 13 modulo 47 is 46 by verifying if \( 13^k \mod 47 \) for \( k \) from 1 to 45 is not 1, and \( 13^{46} \equiv 1 \mod 47 \).

### 2) \( n = 49 \)
- \( n = 49 \) is not a prime number (49 = \( 7^2 \)), so 13 cannot be a primitive root modulo 49.

### 3) \( n = 53 \)
- \( n-1 = 52 \)
- Check if the order of 13 modulo 53 is 52.

### 4) \( n = 59 \)
- \( n-1 = 58 \)
- Check if the order of 13 modulo 59 is 58.

### 5) \( n = 61 \)
- \( n-1 = 60 \)
- Check if the order of 13 modulo 61 is 60.

### 6) \( n = 67 \)
- \( n-1 = 66 \)
- Check if the order of 13 modulo 67 is 66.

Now, let's check these conditions step-by-step.

### Steps:
1. Calculate \( 13^{k} \mod n \) for each \( k \) from 1 to \( n-1 \) for all the prime numbers.
2. Identify the smallest \( k \) such that \( 13^{k} \equiv 1 \mod n \). This is the order of 13 modulo \( n \).
3. If this order is equal to \( n-1 \), then 13 is a primitive root modulo \( n \).

Let’s compute these values for the prime choices.The numbers from the given choices where 13 is a primitive root modulo \( n \) are:

- \( 47 \)
- \( 59 \)
- \( 67 \)

Would you like more details on how these calculations were performed, or do you have any other questions?

Here are 5 related questions to expand on this topic:
1. What are the properties of primitive roots in number theory?
2. How can we find primitive roots for any prime number \( p \)?
3. Why is 13 not a primitive root modulo some other numbers like 49 or 53?
4. What is the significance of the order of a number modulo \( n \)?
5. How does the concept of primitive roots apply in cryptography?

**Tip:** When checking if a number \( g \) is a primitive root modulo \( p \), ensure \( p \) is a prime and verify if the smallest \( k \) such that \( g^k \equiv 1 \mod p \) equals \( p-1 \).

Find the numbers n from the given choices with the property that 13 is a primitive root modulo n.

Explore how to determine which numbers from a given set have 13 as a primitive root modulo n. This problem covers key number theory concepts such as primitive roots and modular arithmetic, with detailed step-by-step analysis. Suitable for undergraduate-level students.

Math Problem Statement

Solution

Ask a new question for Free

By Image

Math Problem Analysis

Mathematical Concepts

Formulas

Theorems

Suitable Grade Level

Related Recommendation