# Finding the orders of 1, 2, .... , 16 (mod 17)

• Kitty Kat
In summary, the problem is to find the lowest value of t that satisfies the congruence nt ≡ 1 (mod 17) for all n ∈ {1, ... , 16}. Using Euler's Theorem, we know that t must be a divisor of φ(17), which is 16. After trying different values of t for each n, we find that only 1, 2, 4, 5, 7, and 8 have a solution. The book's answer key suggests that the solution is 9, but upon further examination, it seems that the book is answering a different question.
Kitty Kat

## Homework Statement

So basically for n ∈ {1, ... , 16}
Find the lowest t to satisfy nt ≡ 1 (mod 17)

## Homework Equations

Euler's Theorem tells us that the order, t, must be a divisor of φ(17), which is Euler's Phi Function.
φ(17) = 16
t ∈ {1, 2, 4, 8, 16}

## The Attempt at a Solution

n = 1
11 ≡ 1 (mod 17)
t = 1

n = 2
I checked 22 and 24 by hand and they weren't congruent to 1 (mod 17).
28 = 64 ≡ 1 (mod 17)
t = 8

n = 4
I checked 42 by hand and it wasn't congruent to 1 (mod 17).
44 = 256 ≡ 1 (mod 17)
t = 4

n = 5
516 = (16 * 16) ≡ 1 (mod 17)
t = 16

My answers seem to be quite different from the answer key, and I'm not sure why.
Also, my textbook's answer key implies that only 1, 2, 4, 5, 7, and 8 actually have a solution; so is there a quick way to verify for which n there is a solution? (Other than checking all the values of t, and finding that none of them satisfy the congruence.)

I know that gcd(n, m) = 1 will have a solution, but 17 is a prime so gcd(n, 17) for all n {1 ... 16} will be 1, which should imply that all n will have a solution?

Thanks!

Last edited:
The answer of the book doesn't make sense, so I did reverse engineering:
If 8 has order 2, then 64=1 mod X, which means X is a divisor of 63 = 7*9. We get the same condition for "2 has order 6" and "4 has order 3".
If 7 has order 3, then X is a divisor of 342 = 2*9*19
If 5 has order 6, then X is a divisor of 15624 = 8*9*7*31.
At this point it gets clear that the book considers X=9.
φ(9) = 6
3 and 6 don't have an order as they share the factor 3 with X=9, all other numbers smaller than 9 are covered in the book's answer. The book simply answers a different question.

Kitty Kat

## What does "mod" mean in finding the orders of numbers?

"Mod" stands for "modulo" and is a mathematical operation that finds the remainder after division. In this context, finding the orders of numbers (mod 17) means finding the remainder when those numbers are divided by 17.

## Why are we finding the orders of numbers (mod 17)?

The concept of finding orders of numbers (mod 17) is important in number theory and modular arithmetic. It helps to understand patterns and relationships between numbers and can be used in various applications such as cryptography.

## What is the significance of finding the orders of numbers (mod 17)?

Finding the orders of numbers (mod 17) can provide insights into the behavior and properties of numbers. For example, it can help determine if a number is a primitive root of another number, or if it has any special properties when used in modular arithmetic.

## How do you find the orders of numbers (mod 17)?

To find the orders of numbers (mod 17), you can use a systematic approach by calculating the powers of the numbers (from 1 to 16) when divided by 17 and finding the first power that returns a remainder of 1. This power is known as the order of that number (mod 17).

## What are some real-life applications of finding the orders of numbers (mod 17)?

One of the main applications of finding the orders of numbers (mod 17) is in cryptography, specifically in the Diffie-Hellman key exchange algorithm. This algorithm relies on the concept of orders of numbers to securely exchange secret keys over a public channel. It is also used in other areas such as coding theory and data compression.

• Calculus and Beyond Homework Help
Replies
6
Views
1K
• Calculus and Beyond Homework Help
Replies
14
Views
925
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
11
Views
2K
• Precalculus Mathematics Homework Help
Replies
5
Views
1K
• Precalculus Mathematics Homework Help
Replies
14
Views
1K
• Calculus and Beyond Homework Help
Replies
4
Views
2K
• Calculus and Beyond Homework Help
Replies
3
Views
779
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
4
Views
1K