Thread: Indices

1.) Find all the solutions of 4^(x) = 13 (mod 17) using indices.

Then, let m be a pos. integer w/ a primitive root r. Also, let a be a pos. integer w/ gcd(a,m) = 1. Through 2.) and 3.), you'll investigate the relationship between ind_(r)a and ind_(r)a^(-1) where a^(-1) is the inverse (multiplicative) of 'a' (mod m)

2.) For each of 3 examples, specify m, r, a. Then find a^(-1), ind_r(a) and ind_(r)a^(-1).

3.) From #2, find a formula relating ind_(r)a and ind_(r)a^(-1). You don't have to prove this.

Hello, flash101!

I'm not familar with "using indices", but here's my version of #1 . . .

1.) Find all the solutions of 4^x .= .13 .(mod 17)

Examine consecutive powers of 4:

. . 4^0 .= .1 .(mod 17)

. . 4^1 .= .4

. . 4^2 .= -1

. . 4^3 .= 13

. . 4^4 .= .1

. . 4^5 .= .4

. . 4^6 .= -1

. . 4^7 .= 13


We see that the mod-17 values are cyclic: 1, 4, -1, 13, . . .

. . and the solutions are: .x = 3, 7, 11, 15, . . .


That is: .x .= .4k - 1, for any integer k.

Originally Posted by Soroban

Hello, flash101!

I'm not familar with "using indices", but here's my version of #1 . . .


Examine consecutive powers of 4:

. . 4^0 .= .1 .(mod 17)

. . 4^1 .= .4

. . 4^2 .= -1

. . 4^3 .= 13

. . 4^4 .= .1

. . 4^5 .= .4

. . 4^6 .= -1

. . 4^7 .= 13


We see that the mod-17 values are cyclic: 1, 4, -1, 13, . . .

. . and the solutions are: .x = 3, 7, 11, 15, . . .


That is: .x .= .4k - 1, for any integer k.

Examples using "indices" include:

11^(x) = 5 (mod 13)

r = 2 (primitive root)

ind_(2)(11^(3x)) = ind_(2)5(mod phi(13))
3xind_(2)11 = ind_(2)5 (mod 12)
3x*7 = 9 (mod 12)
7x = 3 (mod 4)
x = 1 (mod 4)
x = 1, 5, 9 (mod 12)


Another example:

3^(x) = 2 (mod 23)

r = 5

ind_(5)3^(x) = ind_(5)2 = 2 (mod 22)

ind_(5)3^(x) = x ind_(5)3 = 16x (mod 22)
16x = 2 (mod 22) Divide by 2:
8x = 1 (mod 11)
x = 7 (mod 11)
x = 7 or 18 (mod 22)

I have a question about the gcd(a,m) in this type problem.
for example....

7x^20 = = 34(mod 37) [using indices]
I (7x^20) = I(34) (mod 36)
...
...
..
.
20x = 27(mod 36) here I would take the gcd (20,36) = 4 divided by 27/\ therefore there are no solutions???

Is this accurate?

Originally Posted by duggaboy

I have a question about the gcd(a,m) in this type problem.
for example....

7x^20 = = 34(mod 37) [using indices]
I (7x^20) = I(34) (mod 36)
...
...
..
.
20x = 27(mod 36) here I would take the gcd (20,36) = 4 divided by 27/\ therefore there are no solutions???

Is this accurate?

Please post new questions in new threads