So: e(1) = 1, e(12) = 2, but I'm too lazy to do the others by hand:
? znorder(Mod(2,13)) %1 = 12 ? znorder(Mod(3,13)) %2 = 3 ? znorder(Mod(4,13)) %3 = 6 ? znorder(Mod(5,13)) %4 = 4 ? znorder(Mod(6,13)) %5 = 12 ? znorder(Mod(7,13)) %6 = 12 ? znorder(Mod(8,13)) %7 = 4 ? znorder(Mod(9,13)) %8 = 3 ? znorder(Mod(10,13)) %9 = 6 ? znorder(Mod(11,13)) %10 = 12
So 2, 6, 7, and 11 are the primitive roots (four of them, since φ(12) = 4). For part (b):
2. It's just as easy to tackle the general case, which is part (b). First, the index of gk is k, so finding the exponent is equivalent to finding the smallest e such that ek ≡ 0 (mod p-1). If gcd(k,p-1) = 1, then this congruence has the unique solution e ≡ 0 (mod p-1), and the smallest positive solution is e = p-1, so in this case gk is a primitive root. On the other hand, if gcd(k,p-1) = d, then clearly e = (p-1)/d is a solution which is smaller than p-1 and gk is not a primitive root. So we've shown that gk is a primitive root if and only if gcd(k,p-1)=1.
We've also shown, by the way, that e(gk) is at most (p-1)/d, where d = gcd(k,p-1). That'll be useful to remember for problem 7.
Solving parts (a) and (c) is now easy: for (a), the exponents that give primitive roots are 5 and 7; for (c), since 21168 = 243372, they are 5, 11, 13, 17, 19, since every other number less than or equal to 20 is divisible either by 2, by 3, or by 7.
3. If a = b2, then the index of a is twice the index of b, hence even, hence not prime to p - 1. So a can't be a primitive root. 4. Use indices. From problem 21.6, a is a primitive root (mod p) if and only if gcd(I(a),p-1) = 1. In particular, any element with even index can't be a primitive root. This means that the index of a primitive root is odd. Now I(ab) ≡ I(a) + I(b) (mod (p-1)), and the sum of two odd numbers is even. Hence, the product of two primitive roots is never a primitive root.
If we consider the product of three primitive roots, then we're talking I(abc) ≡ I(a) + I(b) + I(c) (mod (p-1)). This will be odd, so for the product to fail to be a primitive root it must share an odd prime factor with p - 1. This can happen for some primes. For example, let p = 19. Then p - 1 = 18, so that the possible indices for primitive roots are 1, 5, 7, 11, 13, 17. Notice, then, that 1 + 5 + 7 = 13, which is prime to p - 1, and 1 + 7 + 13 = 21, which is not. So the product of the three primitive roots g, g5, and g7 is a primitive root, while the product of the three primitive roots g, g7, and g13 is not.
5. If a = gk (mod p), then the index of a is k. As in problem 21.6, we want to find the least positive e such that ke = 0 (mod p-1), so we are looking for the smallest positive e such that ke is a multiple of p - 1. In problem 21.6 we saw that e is at most (p-1)/gcd(k,p-1). It's easy to show, in fact, that no smaller number can work (just divide both sides of the congruence by the gcd and apply the linear congruence theorem). Thus, e = (p-1)/gcd(k,p-1).
Another way to find the answer is to note that ke must be the least common multiple of k and p-1, which is k(p-1)/gcd(k,p-1).
6. Problem 22.1 should have been straightforward. The solutions are (a) x = 5 (mod 37), (b) x= 27 (mod 37), (c) no solutions, (d) x = 10, 14, 23, 27 (mod 37).
Problem 22.2 is more of a pain. Let's see...
? for(n=1,15,print(n," ",Mod(3,17)^n)) 1 Mod(3, 17) 2 Mod(9, 17) 3 Mod(10, 17) 4 Mod(13, 17) 5 Mod(5, 17) 6 Mod(15, 17) 7 Mod(11, 17) 8 Mod(16, 17) 9 Mod(14, 17) 10 Mod(8, 17) 11 Mod(7, 17) 12 Mod(4, 17) 13 Mod(12, 17) 14 Mod(2, 17) 15 Mod(6, 17)so:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 0 | 14 | 1 | 12 | 5 | 15 | 11 | 10 | 2 | 3 | 7 | 13 | 4 | 9 | 6 | 8 |
(Gosh, I hope that's right!) Now part (b) boils down to solving I(4) + I(x) ≡ I(11) (mod 16), i.e., 12 + I(x) ≡ 7 (mod 16), so I(x) ≡ 11 (mod 16), so x ≡ 7 (mod 17). For part (c), it's 5 + 6I(x) ≡ 11 (mod 16), so 6I(x) ≡ 6 (mod 16), which has two solutions, namely I(x) ≡ 1 or 9 (mod 16), which translates back to x ≡ 3 or 14 (mod 17).
7. Again, might as well do (b), which is more general than (a). The point is that what we want to solve, written using indices, is kI(x) ≡ I(a) (mod p-1). So let d = gcd(k,p-1). Then, by the linear congruence theorem from Way Back When, either there are d solutions or there are none. Specifically, there are d solutions if d divides I(a), and there are none if it does not. In part (a), the gcd is k, of course.
For part (c), note that gcd(111,1986) = 3, and 3 divides the index of 729, which is 6. So there are three solutions.
The most interesting part of this is something Silverman doesn't point out, namely that if the gcd is 1, then the congruence always has exactly one solution. This means that the question "which a are k-th powers mod p?" is only interesting in the case that gcd(k,p-1) is not 1.
8. There are four cases to consider: when n is not divisible by 2 or 3, when it is divisible by 2 but not by 3, when it is divisible by 3 but not by 2, and when it is divisible by both. In each case, it's just a matter of writing down what the multiplicativity of φ tells us.
For example, suppose n is divisible by 3 but not by 2. Then write n = 3am, where m is not divisible by 2 or 3. Now
9. Let's say that a number e "is a block length for 1/p" if there is a repeating block of length e in the decimal expansion of 1/p. The period is just the shortest block length.
OK, now suppose that there is a repeating block of length e. Then if we
multiply 1/p by 10e we will get the repeating block as an
integer plus 1/p again. (For example, since 1/3=.333333333...., there is a
repeating block of length 7 in the expansion of 1/3, so that if we multiply
1/3 by 107, we'll get 3333333 + 1/3.)
So the existence of a repeating block of length e is characterized by the
equation 10e x 1/p = integer + 1/p. Multiplying through by p,
this says that 10e ≡ 1 (mod p).
Conversely, if 10e ≡ 1 (mod p), dividing through by p
says that e is a block length for 1/p.
Hence the period, which is the shortest block length, is exactly the
smallest e such that 10e ≡ 1 (mod p), i.e., it is the
order. That gives what we want.