What’s the point in checking lower exponents? Is it just do use their modular residues to help simplify testing the exponent 10 (of course I knoe if you find the ord before checking 10, you don’t need to check 10, but that’s not really the most convenient way)
Checking 10 outright would be misleading in many cases. For example, 3^10 would indeed be 1, but that's because 3^5 was 1. You need to make sure no earlier exponent gives 1.
I think the reason is that if a number r is a primitive root, you can express the group of units U_n as powers of r. And as every primitive root belongs to the group of units (i.e. it has some power that is congruent to 1 mod n), then every primitive root can be expressed as a power of r. Then, we have to have gcd(k,n) = 1, since if the gcd = d > 1, we would have ord(r^k) = ord(r)/d = φ(n)/d < φ(n), and hence r^k would *not* be a primitive root. If you replace r = 7, n = 22 and φ(n) = 10, then that explanation be specific to the problem in this video.
@@PunmasterSTP Yes, i know see why we must have this, in a previous proposition Michael built that ord(a^k) = ord(a)/gcd(k,ord(a)). For a^k to be a primitive root, we must have ord(a^k) = phi(n). But since a is a primitive root, we have ord(a) = phi(n), from which we see we must have gcd(k, ord(a)) = 1, but this is precisely the same as gcd(k,phi(n))=1
Professor Penn, thank you for a massive demonstration of all the Primitive Roots of 22.
These are amazing demonstrations, and I'm rooting for you all the way!
These videos are really excellent.
Thanks for the video! Efficient way to find primitive roots modulo
Thanks for this,,very helpful
I love to learn from you
What’s the point in checking lower exponents? Is it just do use their modular residues to help simplify testing the exponent 10 (of course I knoe if you find the ord before checking 10, you don’t need to check 10, but that’s not really the most convenient way)
Checking 10 outright would be misleading in many cases. For example, 3^10 would indeed be 1, but that's because 3^5 was 1. You need to make sure no earlier exponent gives 1.
why is the general form of the primitive roots 7^k, where gcd(k,10) = 1 exactly?
I think the reason is that if a number r is a primitive root, you can express the group of units U_n as powers of r. And as every primitive root belongs to the group of units (i.e. it has some power that is congruent to 1 mod n), then every primitive root can be expressed as a power of r. Then, we have to have gcd(k,n) = 1, since if the gcd = d > 1, we would have ord(r^k) = ord(r)/d = φ(n)/d < φ(n), and hence r^k would *not* be a primitive root.
If you replace r = 7, n = 22 and φ(n) = 10, then that explanation be specific to the problem in this video.
@@PunmasterSTP Yes, i know see why we must have this, in a previous proposition Michael built that ord(a^k) = ord(a)/gcd(k,ord(a)). For a^k to be a primitive root, we must have ord(a^k) = phi(n). But since a is a primitive root, we have ord(a) = phi(n), from which we see we must have gcd(k, ord(a)) = 1, but this is precisely the same as gcd(k,phi(n))=1