The exercise was a good one. Given Phi is multiplicative we separate the input n by it's prime powers. Then it was only a matter of finding all combinations of primes that yield 24. Making a table of phi with prime powers really helps.
If 3 divides phi(n) then 3 must divide n, since phi(n) = Pi(p_i-1)Pi(p_i^(a_i-1)) so either p_i-1 = 3 or p_i = 3 for some i (and 4 is not prime). From there, we know that 3^2 is the exponent of 3, which contributes 2*3 to phi(n), and we just need to find the power of 2 that contributes the remaining 2^2 to phi(n) and n=2^3*3^2 = 72 is the only answer.
3 can divide phi(n) without dividing n. For example, phi(7)=6. In fact, 3 divides phi(p) for all p = 1 (mod 3). That's why 72 is not the only the n with phi(n)=24.
Wow - after this correction, there are so many! All the powers of primes where phi(p^k) divides 24 work - phi(13) = 12, phi(7) = 6, phi(5) = 4, phi(2^k) = 2^(k-1), phi(3)=2, phi(3^2) = 6 - so 39, 52, 78 all work with 13 as a factor, 35, 56, 70, 84 work with 7 as a factor, and 45 and 90 also work with 5 as a factor, plus the aforementioned 72. I think these are the only 10 solutions.
@@dneary For what it's worth I only found these 10. I used that the divisors of 24 are d = [1,2,3,4,6,8,12,24] then looked for all phi(p^k) in d phi(2^k) = 2^(k-1) [1,2,4,8] phi(3) = 2 phi(3^2) = 6 phi(5) = 4 phi(7) = 6 phi(13) = 12 Then all that remains is combining them correctly. We have interesting ones with 5 * 7 = 35 3 * 13 = 39 3^2 * 5 = 45 2^2 * 13 = 52 2^3 * 7 = 56 2^3 * 3^2 = 72 2^2 * 3 * 7 = 84 Then we can use that phi(2) = 1 to get three more by multiplying the solutions which dont already have a factor of two 2 * 5 * 7 = 70 2 * 3 * 13 = 78 2 * 3^2 * 5 = 90
@@dneary Yeah you got all the solutions. A natural generalization to ask is how many possible values of n satisfy phi(n)=k for a particular k. Carmichael's conjecture asserts that there are no k with exactly one corresponding n.
Hi Dr. Borcherds. You might talk about this later, but I went hunting for a more rigorous derivation of the product formula for Euler's totient function and this turns out to be a very nice application of the Chinese remainder theorem.
Figured I'd give the exercise a shot. Think I got it. 7*5, 13*3, 7*5*2, 13*3*2, 13*4, 7*8, 7*3*4, 5*3*3, 5*3*3*2, 3*3*8 (35,39,45,52,56,70,72,78,84,90) These were found by finding prime p where (p-1) is a factor of 24, then multiplying several (p-1) together to make a factor of 24 (multiplying by an appropriate factor of 2 or 3 afterward when necessary). I don't think I missed any but I wasn't being too comprehensive. All values need to not divide any primes except 2, 3, 5, 7, or 13, and I think I got every possibility that ends up working.
e = pi = 3 = log(log(n)). My knowledge of engineering has improved so much!
Make sure you use the approximation pi = 3 when designing that new bridge or airplane *wink wink*
Could you please sir explain anabelian geometry
We can't thank you enough, Sir!
The exercise was a good one. Given Phi is multiplicative we separate the input n by it's prime powers.
Then it was only a matter of finding all combinations of primes that yield 24.
Making a table of phi with prime powers really helps.
If 3 divides phi(n) then 3 must divide n, since phi(n) = Pi(p_i-1)Pi(p_i^(a_i-1)) so either p_i-1 = 3 or p_i = 3 for some i (and 4 is not prime). From there, we know that 3^2 is the exponent of 3, which contributes 2*3 to phi(n), and we just need to find the power of 2 that contributes the remaining 2^2 to phi(n) and n=2^3*3^2 = 72 is the only answer.
3 can divide phi(n) without dividing n. For example, phi(7)=6. In fact, 3 divides phi(p) for all p = 1 (mod 3). That's why 72 is not the only the n with phi(n)=24.
@@grpthry4659 Good point! I need to think more, obviously. You can limit it to primes that are of the form 2^k.3 + 1 then (in addition to p=3).
Wow - after this correction, there are so many! All the powers of primes where phi(p^k) divides 24 work - phi(13) = 12, phi(7) = 6, phi(5) = 4, phi(2^k) = 2^(k-1), phi(3)=2, phi(3^2) = 6 - so 39, 52, 78 all work with 13 as a factor, 35, 56, 70, 84 work with 7 as a factor, and 45 and 90 also work with 5 as a factor, plus the aforementioned 72. I think these are the only 10 solutions.
@@dneary For what it's worth I only found these 10. I used that the divisors of 24 are d = [1,2,3,4,6,8,12,24] then looked for all phi(p^k) in d
phi(2^k) = 2^(k-1) [1,2,4,8]
phi(3) = 2
phi(3^2) = 6
phi(5) = 4
phi(7) = 6
phi(13) = 12
Then all that remains is combining them correctly. We have interesting ones with
5 * 7 = 35
3 * 13 = 39
3^2 * 5 = 45
2^2 * 13 = 52
2^3 * 7 = 56
2^3 * 3^2 = 72
2^2 * 3 * 7 = 84
Then we can use that phi(2) = 1 to get three more by multiplying the solutions which dont already have a factor of two
2 * 5 * 7 = 70
2 * 3 * 13 = 78
2 * 3^2 * 5 = 90
@@dneary Yeah you got all the solutions. A natural generalization to ask is how many possible values of n satisfy phi(n)=k for a particular k. Carmichael's conjecture asserts that there are no k with exactly one corresponding n.
Is there a nice algebro-geometric interpretation of a multiplicative function?
Great Video, Thanks.
Thank you for teaching 😊 us sir
Hi Dr. Borcherds. You might talk about this later, but I went hunting for a more rigorous derivation of the product formula for Euler's totient function and this turns out to be a very nice application of the Chinese remainder theorem.
72
If n = exp(exp(t)), Log(Log(n)) = t. The commentary that it is practically 3 seems silly.
If you want more factors than order 1 on average for a random number, you can't store the digits reasonably.
log(log(10^8)) is just less than 3 and if you increase 10^8 by 15 orders of magnitude, log(log(10^23)) is still 3.something
yeeee
gnag xis esab
Figured I'd give the exercise a shot. Think I got it.
7*5, 13*3, 7*5*2, 13*3*2, 13*4, 7*8, 7*3*4, 5*3*3, 5*3*3*2, 3*3*8
(35,39,45,52,56,70,72,78,84,90)
These were found by finding prime p where (p-1) is a factor of 24, then multiplying several (p-1) together to make a factor of 24 (multiplying by an appropriate factor of 2 or 3 afterward when necessary).
I don't think I missed any but I wasn't being too comprehensive. All values need to not divide any primes except 2, 3, 5, 7, or 13, and I think I got every possibility that ends up working.
Got that too!