4:15 slight correction, all residues relatively prime to n can be achieved by a power of the primitive root. If n is a prime itself, then all residues can be achieved, but here n is not necessarily prime, however the proof is still perfect
This number theory course is a lot different than the one I took in college. I think because ours had a cryptography/applied kind of slant and maybe also it’s covering material at a faster pace.
The first warmup problem is x = 2 mod 7, and the second one is a tricky one. You need to use the primitive root 7 instead of 3. Hence, you get x = 13 by the lemma.
Think I'm going to stop here. I might return in the future but it's getting too advanced for me, though I'm glad I got this far. Thanks for your excellent course on number theory, Professor Penn!
The table of powers of 2 mod 19 is much easier to calculate and handle if, instead of working with just the positive residues, you set the results to {-9, -8, -7, ... , 7, 8, 9}. (Notice for instance 10 = -9 mod 19, 9 = -8 mod 19, etc). Using this set gives you very nice symmetries when calculating those powers of 2. Specifically, the table becomes n : 2ⁿ 1 : 2 2 : 4 3 : 8 4 : -3 5 : -6 6 : 7 7 : -5 8 : 9 9 : -1 (Notice that the rest of the table below will just be 1 through 8 with the sign flipped) 10 : -2 11: -4 12: -8 13: 3 14: 6 15: -7 16: 5 17: -9 18: 1 So the original problem was find x such that 5ˣ = 17 mod 19. But that's the same as 5ˣ = -2 mod 19. As in the video, 2¹⁶ = 5 mod 19, and 2¹⁰ = -2 mod 19 so (2¹⁶)ˣ = 2¹⁰ mod 19. Since φ(19) = 18, we have => 16x = 10 mod 18 => 8x = 5 mod 9 => -x = 5 mod 9 => x = -5 = 4 mod 9 Generally speaking you can simplify the calculation in these sorts of modular arithmetic problems by swapping (n-x) for x when working mod n if x is more than half of n. In this problem for instance it literally cuts the calculation time in half for figuring out that table.
16 is a solution, as is every integer of the form (7k+2), i.e. x ≡ 2 mod 7 You can check this by observing that 2(7k+2)^5 = 2(2^5 + 7k*5*2^4 + ...) by the binomial expansion, and all of the terms apart from the first one have a factor of 7, so are congruent to 0 mod 7. So 2(7k+2)^5 ≡ 2*2^5 mod 7 ≡ 64 mod 7 ≡ 1 mod 7 giving x = 7k+2. That sort of solution is normal for all congruence equations of the first type. For the second one, if x=3, then 7^3 = 343 ≡ 3 mod 17, so it's not a solution. Have a look at my comment "Spoiler alert" and see if the tips I gave are any help to you.
Since 113 is prime, a^112 ≡ 1 mod 113, so a^270 = (a^112)^2 * (a^46) ≡ (a^46) mod 113. So we only need to solve a^46 ≡ 37 mod 113. To find primitive roots mod 113, we only need check that the powers (112/2) = 56 and (112/7) = 16 are not congruent to 1 mod 113. Try 37^56 ≡ 112 mod 113 and 37^7 ≡ 42 mod 113, so 37 is a primitive root of 113. Set a = 37^b, so 37^46b ≡ 37 mod 113. Since 37 = 37^1, we can "take logs": 46b ≡ 1 mod 112. So 46b = 112k + 1. But the LHS is even and the RHS is odd, so there are no integer solutions.
Spoiler alert. For those who want to check their answers to the warm-ups. Solve: 2x^5 ≡ 1 mod 7. A solution is x = 2. Note the following: 2^(-1) ≡ 4 mod 7, so solve x^5 ≡ 4 mod 7. 3 is the smallest primitive root of 7. 3^4 ≡ 4 mod 7 If you have x ≡ 3^2 mod 7, then x ≡ 2 mod 7. Solve: 7^x ≡ 6 mod 17. A solution is x = 13. Note the following: 3 is the smallest primitive root of 17. 3^11 ≡ 7 mod 17 and 3^15 ≡ 6 mod 17. The multiplicative inverse of 11 mod 16 is 3.
regarding your last line, we don't want the multiplicative inverse of 11 mod 16 because we're solving 11x = 15 mod 16, i.e., we have 11x = -1 mod 16, whereas the inverse is the solution to 11x = 1 mod 16.
@@knivesoutcatchdamouse2137 You're trying to solve the equation in one step, which is fine. But in general, when we try to solve ax ≡ b mod n, we find the multiplicative inverse of a (mod n) and multiply both sides of the equation by it. That is the modular arithmetic equivalent of dividing each side by a. We get: a^(-1).ax ≡ a^(-1).b (mod n) x ≡ a^(-1).b (mod n) This is our solution because a^(-1).a = 1 In this case, I gave the multiplicative inverse of 11 (mod 16), not as the solution, but to help you in the first step. So we have: 11x ≡ 15 (mod 16) 3.11x ≡ 3.15 (mod 16) -- this is equivalent to "dividing" both sides by 11. 33x ≡ 45 (mod 16) x ≡ 13 (mod 16) Note that 33 ≡ 1 (mod 16). That method will work for any values of the constants that I called a and b earlier, rather than just when b = 1.
@@RexxSchneider Ah. Yes I misunderstood you as saying that would give you the solution. I should have recognized you were alluding to the next step in obtaining the solution. Not my finest hour, haha! Thank you for your reply.
2:31 Another proof of reverse direction. Given gcd(m, ϕ(n)) = 1 and that the order of r mod n is ϕ(n). First note that (r^m)^ϕ(n) = (r^ϕ(n))^m = 1 mod n. Need to show that n∤(r^m)^a - 1 when 1≤a≤ ϕ(n)-1. Let a= ϕ(n)-t where 1≤t≤ϕ(n)-1. (r^m)^a - 1 = r^(mϕ(n) - mt)-1. since gcd(m, ϕ(n)) = 1 , mx+ϕ(n)y=1 for some integers x and y -----> t mx+tϕ(n)y=t. This shows that ϕ(n)∤mt, hence ϕ(n)∤mϕ(n) - mt, so n∤ r^(mϕ(n) - mt)-1
4:15 slight correction, all residues relatively prime to n can be achieved by a power of the primitive root. If n is a prime itself, then all residues can be achieved, but here n is not necessarily prime, however the proof is still perfect
slight correction to your slight correction: if n is a prime then all non-zero residues can be achieved by powers of a primitive root
9:16 should be a = b mod phi(n) in the forward proof, right?
Yes
25:36 Homework
25:57 Good Place To Stop
This number theory course is a lot different than the one I took in college. I think because ours had a cryptography/applied kind of slant and maybe also it’s covering material at a faster pace.
The first warmup problem is x = 2 mod 7, and the second one is a tricky one. You need to use the primitive root 7 instead of 3. Hence, you get x = 13 by the lemma.
Think I'm going to stop here. I might return in the future but it's getting too advanced for me, though I'm glad I got this far. Thanks for your excellent course on number theory, Professor Penn!
The table of powers of 2 mod 19 is much easier to calculate and handle if, instead of working with just the positive residues, you set the results to {-9, -8, -7, ... , 7, 8, 9}. (Notice for instance 10 = -9 mod 19, 9 = -8 mod 19, etc). Using this set gives you very nice symmetries when calculating those powers of 2. Specifically, the table becomes
n : 2ⁿ
1 : 2
2 : 4
3 : 8
4 : -3
5 : -6
6 : 7
7 : -5
8 : 9
9 : -1 (Notice that the rest of the table below will just be 1 through 8 with the sign flipped)
10 : -2
11: -4
12: -8
13: 3
14: 6
15: -7
16: 5
17: -9
18: 1
So the original problem was find x such that 5ˣ = 17 mod 19. But that's the same as 5ˣ = -2 mod 19.
As in the video, 2¹⁶ = 5 mod 19, and 2¹⁰
= -2 mod 19 so
(2¹⁶)ˣ = 2¹⁰ mod 19. Since φ(19) = 18, we have
=> 16x = 10 mod 18 => 8x = 5 mod 9 => -x = 5 mod 9 => x = -5 = 4 mod 9
Generally speaking you can simplify the calculation in these sorts of modular arithmetic problems by swapping (n-x) for x when working mod n if x is more than half of n. In this problem for instance it literally cuts the calculation time in half for figuring out that table.
good video as always 😊
I wonder if phi^2 (n) would be a good notation... 🤔
Super!
the first warmup question i got x = 16 and i verified it to be right. However, the second one i get x = 3 ( mod 8 ) and it does not seem to be right.
16 is a solution, as is every integer of the form (7k+2), i.e. x ≡ 2 mod 7 You can check this by observing that 2(7k+2)^5 = 2(2^5 + 7k*5*2^4 + ...) by the binomial expansion, and all of the terms apart from the first one have a factor of 7, so are congruent to 0 mod 7. So 2(7k+2)^5 ≡ 2*2^5 mod 7 ≡ 64 mod 7 ≡ 1 mod 7 giving x = 7k+2. That sort of solution is normal for all congruence equations of the first type.
For the second one, if x=3, then 7^3 = 343 ≡ 3 mod 17, so it's not a solution. Have a look at my comment "Spoiler alert" and see if the tips I gave are any help to you.
Please Michael helps here on number theory
Find a such that 0
Since 113 is prime, a^112 ≡ 1 mod 113, so a^270 = (a^112)^2 * (a^46) ≡ (a^46) mod 113. So we only need to solve a^46 ≡ 37 mod 113.
To find primitive roots mod 113, we only need check that the powers (112/2) = 56 and (112/7) = 16 are not congruent to 1 mod 113.
Try 37^56 ≡ 112 mod 113 and 37^7 ≡ 42 mod 113, so 37 is a primitive root of 113.
Set a = 37^b, so 37^46b ≡ 37 mod 113. Since 37 = 37^1, we can "take logs":
46b ≡ 1 mod 112.
So 46b = 112k + 1. But the LHS is even and the RHS is odd, so there are no integer solutions.
Spoiler alert.
For those who want to check their answers to the warm-ups.
Solve: 2x^5 ≡ 1 mod 7. A solution is x = 2.
Note the following:
2^(-1) ≡ 4 mod 7, so solve x^5 ≡ 4 mod 7.
3 is the smallest primitive root of 7.
3^4 ≡ 4 mod 7
If you have x ≡ 3^2 mod 7, then x ≡ 2 mod 7.
Solve: 7^x ≡ 6 mod 17. A solution is x = 13.
Note the following:
3 is the smallest primitive root of 17.
3^11 ≡ 7 mod 17 and 3^15 ≡ 6 mod 17.
The multiplicative inverse of 11 mod 16 is 3.
regarding your last line, we don't want the multiplicative inverse of 11 mod 16 because we're solving 11x = 15 mod 16, i.e., we have 11x = -1 mod 16, whereas the inverse is the solution to 11x = 1 mod 16.
@@knivesoutcatchdamouse2137 You're trying to solve the equation in one step, which is fine. But in general, when we try to solve ax ≡ b mod n, we find the multiplicative inverse of a (mod n) and multiply both sides of the equation by it. That is the modular arithmetic equivalent of dividing each side by a. We get:
a^(-1).ax ≡ a^(-1).b (mod n)
x ≡ a^(-1).b (mod n)
This is our solution because a^(-1).a = 1
In this case, I gave the multiplicative inverse of 11 (mod 16), not as the solution, but to help you in the first step. So we have:
11x ≡ 15 (mod 16)
3.11x ≡ 3.15 (mod 16) -- this is equivalent to "dividing" both sides by 11.
33x ≡ 45 (mod 16)
x ≡ 13 (mod 16)
Note that 33 ≡ 1 (mod 16). That method will work for any values of the constants that I called a and b earlier, rather than just when b = 1.
@@RexxSchneider Ah. Yes I misunderstood you as saying that would give you the solution. I should have recognized you were alluding to the next step in obtaining the solution. Not my finest hour, haha! Thank you for your reply.
I don't understand the difference between writing the equal with 2 or 3 dashes
2:31 Another proof of reverse direction.
Given gcd(m, ϕ(n)) = 1 and that the order of r mod n is ϕ(n). First note that (r^m)^ϕ(n) = (r^ϕ(n))^m = 1 mod n.
Need to show that n∤(r^m)^a - 1 when 1≤a≤ ϕ(n)-1.
Let a= ϕ(n)-t where 1≤t≤ϕ(n)-1.
(r^m)^a - 1 = r^(mϕ(n) - mt)-1.
since gcd(m, ϕ(n)) = 1 , mx+ϕ(n)y=1 for some integers x and y -----> t mx+tϕ(n)y=t. This shows that ϕ(n)∤mt, hence ϕ(n)∤mϕ(n) - mt, so n∤ r^(mϕ(n) - mt)-1