Number Theory (2) Homework: Find Integer Orders Modulo 19 & 17

[Shackleford]

Homework Statement

1. Find an integer modulo 19 with each of the following orders of 2 and 3.

2. Find all integers modulo 17 such that its order modulo 17 is 4.

Homework Equations

The multiplicative order of a modulo n, denoted by ord_n(a), is the smallest integer k > 0 such that a^k ≡ 1 (mod n), when gcd(a,n) = 1 and n > 1.

The Attempt at a Solution

1) I want to find an integer a such that

a² ≡ 1 (mod 19), a = 18;

a³ ≡ 1 (mod 19), a = 7.

2) I'm looking at ord₁₇(a) = 4.

Well, two is a primitive root modulo 17, so

ord₁₇(2^j) = ord₁₇(2)/gcd(8, j) = 8/ gcd(8, j) which implies that j = 6.

2⁶ ≡ 13 (mod 17), so a = 30 + 17k.

 

[Dick]

Homework Statement

1. Find an integer modulo 19 with each of the following orders of 2 and 3.

2. Find all integers modulo 17 such that its order modulo 17 is 4.

Homework Equations

The multiplicative order of a modulo n, denoted by ord_n(a), is the smallest integer k > 0 such that a^k ≡ 1 (mod n), when gcd(a,n) = 1 and n > 1.

The Attempt at a Solution

1) I want to find an integer a such that

a² ≡ 1 (mod 19), a = 18;

a³ ≡ 1 (mod 19), a = 7.

2) I'm looking at ord₁₇(a) = 4.

Well, two is a primitive root modulo 17, so

ord₁₇(2^j) = ord₁₇(2)/gcd(8, j) = 8/ gcd(8, j) which implies that j = 6.

2⁶ ≡ 13 (mod 17), so a = 30 + 17k.

I don't think you've actually asked a question. But a=4 works as well, that's not of the form 30+17k. Try to find where you missed that one.

 

[Shackleford]

I don't think you've actually asked a question. But a=4 works as well, that not of the form 30+17k. Try to find where you missed that one.

Sorry. I just wanted to make sure that I was construing the questions correctly. I'll take a look.

Ah. I forgot gcd(8, j = 2) = 2.