this number is "super divisible"

Рет қаралды 8,705

Michael Penn

Күн бұрын

Пікірлер: 43

@prometheus3375 4 күн бұрын

8:49 but the lcm(2, 6) is 6.

@wolffang21burgers 4 күн бұрын

Which is funny because his example was exactly LCM(2,6) at 3:30

@rainerzufall42 4 күн бұрын

@@wolffang21burgers I think, he does this intentionally.

@Neodynium.the_permanent_magnet 4 күн бұрын

@rainerzufall42 Mistake-bait! So that you (and I) add comments to the video ...

@tolberthobson2610 2 күн бұрын

I thought i was crazy when he said 12... the LCM(2, 6) = 6

@rainerzufall42 2 күн бұрын

@@Neodynium.the_permanent_magnet Yes, I know that quite well!

@demenion3521 4 күн бұрын

just a minute into the video and i'm confused by the definition of λ. after a short google search, it turns out that the definition is just wrong, it's supposed to be the minimal value of m s.t. a^m=1 (mod n), not a^λ(m)

@aleksapupovac 4 күн бұрын

That was what my guess had been

@epic_win 4 күн бұрын

I got to admit, definition from the video made me immediately respect Carmichael. Shame it's not correct.

@GreenMeansGOF 4 күн бұрын

I was confused but I just assumed that it was a recursive definition where you need smaller values of lambda to calculate higher values. Good catch though.

@ericslavich4297 4 күн бұрын

Thank you.

@leif1075 4 күн бұрын

@@epic_winwhy did it make you respect if it's confusing shiuldnt that make youbrespect him less..and if this is confusing shouldnt it be banished .at least til it's clarified .math has enough of thia stuoid bullshit confusion alreadybthat is not smart or clear or useful or logical..you can marrly dolve this by saying ok this is clearly divisible by 7 so the smallest natural number that doesnt divide this nust be between 2 and 6 obviously..didnt amyone else do this..and since two odds aubtracted give am even itbia divisible by 2..so isnt the answer 1? Since wven if its nkt divislbe by 3 3 is bigge rthan 2

@Bodyknock 4 күн бұрын

6:45 Once you’ve determined that λ₄ is at least 4 then you can, instead of trying n’s one by one, try to reverse engineer n that satisfies the condition using the properties of λ mentioned earlier in the video. For λ₄ = 4, we want m such that λ(m) = 4. Per the video, For all odd primes p λ(p) = p-1, so λ(5) = 4. However we need this to be even (because λ is always even except for λ(2) = λ(1) = 1), so 5 won’t work. But 5*2 does work since lcm(λ(2), λ(5)) = lcm(1,4) = 4, so we can use λ₃ = 10. For λ₃ = 10, similar to above note that λ(11) = 10. But we can’t use 11, so we’ll instead use 2*11 and get λ(22) = 10, so we’ll set λ₂ = 22. And again, like above, λ(23) = 22, but since we’ll need an even value, we can use 23*2 =46 for λ. And finally, λ(47) = 46. This time however, since we’re at last “at the bottom of the tower”, we can actually use an odd number here since we don’t need to worry about finding a new λ(n) = 47. So the bottom number is 47. And there you go, we reduce the exponents mods 4, 10, 22, 46, and 47 just like in the video. And since at each stage we selected the smallest value which produced the desired λ it’s also going to be the minimum one.

@curtiswfranks 4 күн бұрын

Is this guaranteed to be minimal? Or does it mean that we must check primes up to and including, but not beyond, 47?

@안태영-g8w 4 күн бұрын

Related fact: 47 is a safe prime. If a prime number p=2q+1 is a 「safe prime」 so that q is also prime, then λ(p)=p-1=2q and λ_2(p)=λ(2q)=q-1. That is, λ_2(p) is almost half of p. If p is not safe, on the other hand, λ_2(p) is smaller than a quarter of p, which implies that the value decreases faster. 47 is the strong case that the value decreases slowly as being applied by λ multiple times. (47=23·2+1, 23=11·2+1, 11=5·2+1, 5=2·2+1)

@Czeckie 4 күн бұрын

7:05 shouldn't we care about congruency mod a power of prime also? The lambda4 should be computed for 32, 27 and 25 too. We were 'a bit' lucky, since they are not congruent modulo 3^5, but this technique checking just primes wouldn't find it.

@GreenMeansGOF 4 күн бұрын

Could Euler’s Totient function also be used to solve this problem?

@deinauge7894 4 күн бұрын

7:00 that's wrong? eg. the smallest natural number not deviding 6 is 4. Not a prime, but a prime power.

@robertveith6383 4 күн бұрын

* *dividing*

@MichaelRothwell1 2 күн бұрын

Right. Michael doesn't address the issue of whether the number is divisible by 4, 8, 16, 32, or any other number less than 47 with a repeated prime factor. But the use of the Carmichael λ-function is pretty cool!