Modulo = preposition 9:29 Residue of 9 is sum of all digits. Calculation technique for mod 9 11:41 Calculation technique for mod 11 12:22 Last digit of square of a = last digit of square of last digit of a 15:06 The last digit of a^2+b^2+c^2 depends on the last digit of a,b,c. By comparing the last digits, we can test whether a number can be written by the form a^2 + b^2 + c^2 mod 8. 16:47 For any a of Z/9Z, (a + 3)^3 = a^3 ( mod 9) from which any x^3 of Z/9Z is congruent to -1,0,1. So, possible a^3 + b^3 + c^3 = sum of three elements of {1, 0, 1} = -3,-2,-1,0,1,2,3. Thus 4 and 5 cannot be written by sum of three squares in Z/9Z. 18:22 ~ Fermat If p is prime, a^p = a (mod p). If p is not prime, it failes. 2^6 is not congruent to 4 which is not congruent to 2 modulo 6. 20:13 Application of Fermat’s theorem Show that (1/5)n^5 + (1/3)n^3 + (7/15)n is integer. Because (1/5)n^5 + (1/3)n^3 + (7/15)n = (1/15)(3n^5 + 5n^3 +7n), it suffices to show that 3n^5 + 5n^3 +7n is divisible by 15. By Fermat’ theorem n^3 = n (mod 3), so 3n^5 + 5n^3 +7n = 3n^5 + 5 n + 7n = 0 mod 3. By Fermat’ theorem n^5 = n (mod 5), so 3n^5 + 5n^3 +7n = 3n + 5 ^3n + 7n = 0 mod 5. Thus, 3n^5 + 5n^3 +7n is divisible by 3 and 5, that is by 15. 20:35 PROOF of Fermat’s theorem 0^p = 0 (mod p). 1^p = 1 (mod p) 2^p = (1+1)^p = 1^p + 1^p = 1+1=2 (mod p) 3^p = (2+1)^p = 2^p + 1^p = 2+1 =3 (mod p) Suppose the hypothesis of mathematical induction, that is n^p = n (mod p). Using the formula (x+y)^p = x^p + y^p ( mod p) as (n+1)^p = n^p +1 (mod p), (n+1)^p = n^p +1=n+1 (mod p). 25:28 Application of Fermat’s theorem Using the contraposition of Fermat’s theorem, we can check whether a given number is prime or not. For example, if 2^35 is not congruent to 2 modulo 35, then 35 is not prime. I do not understand the 1-st speed up technique at 27;44. 31:47 Even if a^p = a (mod p) for any a, somtimes p is not a prime. Carmichael number 561 is not prime and satisfies a^561 = a (mod 561) for any number a. By the following three equations a^561 = a (mod 3), a^561 = a (mod 11), a^561 = a (mod 17), we get a^561 = a (mod 3*11*17). In fact, since 3,11,17 are coprime, a^561 - a = 3q = 11q’ = 17Q implies that a^561 -a = 3*11*17Q’. 38:11 Let p be a prime number. LEMMA. If p divides n^2+1, then p = 2 in Z or p = 1 (mod 4). PROOF By the assumption, n^2 = -1 (mod p). Because p is prime, p is odd. By Fermat’s theorem, in Z/pZ, 1 = n^(p-1) = (-1)^( (p-1)/2 ) = -1 if (p-1)/2 is odd or 1 if (p-1)/2 is even (p = 1 mod 4). Note that 1 = -1 (mod p) occurs only in case of p =2. Thus, we proved the lemma. Application of the above lemma. The following corollary means that there are infinitely many primes congruent to 1 modulo 4. COROLLARY. If p(1),…,p(k) are primes and all of them are congruent to 1 modulo 4 , then each prime factor of ( 2p(1)*…*p(k) )^2 + 1 is a new prime congruent to 1 modulo 4. PROOF. Consider prime factors q(1),..,q(n) of ( 2p(1)*…*p(k) )^2 + 1, that is, ( 2p(1)*…*p(k) )^2 + 1 is represented by powers of q(1),..,q(n). Then the factors has the following properties. 1) Each of q(1),..,q(n) is congruent to 1 modulo 4 or equal to 2. 2) Each of q(1),..,q(n) is not equal to 2, p(1),…,p(k). The first property follows from the above lemma, since each of prime q(i) divides ( 2p(1)*…*p(k) )^2 + 1 which has the form N^2 +1. To show second property, e.g., suppose that q(1) = p(1), then p(1) divides ( 2p(1)*…*p(k) )^2 + 1 and hence p(1) divides 1, which is contradiction. Thus we proved.
I didn't know that proof of Fermat's little theorem! I only knew the proof using Lagrange's theorem. My favorite modulo trick uses the fact that 1001 = 7 * 11 * 13. We can use 1000 = -1 mod 1001 to check if very large integers are divisible by 7, 11 , and 13 all at once. e.g. 12,343,827 = 827 - 343 + 12 = 496 mod 1001 Now we have 12,343,827 = 496 = 6 mod 7 12,343,827 = 496 = 1 mod 11 12,343,827 = 496 = 2 mod 13
It's good to see that fields medalist contributing some of his time on undergraduate and senior ug lectures. Earlier some of your videos are difficult to understand and they assume some familiarity with those topics already before watching. But now with your increasing Playlist we can hope some serves as Playlist for your graduate lecture videos.
I'm surprised that Prof. Borcherds doesn't know about the Vedic divisibility rules. To test divisibility by 7 take the ones' digit multiplied by either (as a matter of convenience to the calculation) -2 or +5; and add it to the remaining digits shifted right one space. So one tests 343 by taking either -6 (as 3 * -2) or 15 (as 3 * +5) and adding it to 34 to get respectively 28 or 49: both of which are divisible by 7 confirming that 343 is also. Unfortunately this doesn't readily preserve the modulus, though it can be regenerated from the cycle count. This technique works for all divisors d, with the multiplier determined as ceiling of one tenth the smallest multiple of d with a ones digit of 9 (or that number minus d when subtraction is more convenient). Thus the multiplier for 13 is ceiling(39/10) = 4 (or -9) and that for 17 is ceiling(119/10) = 12 (or -5) , etc. Note this gives a multipliers of -1 for 11 and +1 for 9, both equivalent to the traditional divisibility test for both of them.
Modulo = preposition
9:29 Residue of 9 is sum of all digits. Calculation technique for mod 9
11:41 Calculation technique for mod 11
12:22
Last digit of square of a = last digit of square of last digit of a
15:06 The last digit of a^2+b^2+c^2 depends on the last digit of a,b,c. By comparing the last digits, we can test whether a number can be written by the form a^2 + b^2 + c^2 mod 8.
16:47
For any a of Z/9Z, (a + 3)^3 = a^3 ( mod 9) from which any x^3 of Z/9Z is congruent to -1,0,1.
So, possible a^3 + b^3 + c^3 = sum of three elements of {1, 0, 1} = -3,-2,-1,0,1,2,3. Thus
4 and 5 cannot be written by sum of three squares in Z/9Z.
18:22 ~ Fermat
If p is prime, a^p = a (mod p).
If p is not prime, it failes. 2^6 is not congruent to 4 which is not congruent to 2 modulo 6.
20:13 Application of Fermat’s theorem
Show that (1/5)n^5 + (1/3)n^3 + (7/15)n is integer.
Because (1/5)n^5 + (1/3)n^3 + (7/15)n = (1/15)(3n^5 + 5n^3 +7n), it suffices to show that 3n^5 + 5n^3 +7n is divisible by 15.
By Fermat’ theorem n^3 = n (mod 3), so 3n^5 + 5n^3 +7n = 3n^5 + 5 n + 7n = 0 mod 3.
By Fermat’ theorem n^5 = n (mod 5), so 3n^5 + 5n^3 +7n = 3n + 5 ^3n + 7n = 0 mod 5.
Thus, 3n^5 + 5n^3 +7n is divisible by 3 and 5, that is by 15.
20:35 PROOF of Fermat’s theorem
0^p = 0 (mod p).
1^p = 1 (mod p)
2^p = (1+1)^p = 1^p + 1^p = 1+1=2 (mod p)
3^p = (2+1)^p = 2^p + 1^p = 2+1 =3 (mod p)
Suppose the hypothesis of mathematical induction, that is n^p = n (mod p).
Using the formula (x+y)^p = x^p + y^p ( mod p) as (n+1)^p = n^p +1 (mod p),
(n+1)^p = n^p +1=n+1 (mod p).
25:28 Application of Fermat’s theorem
Using the contraposition of Fermat’s theorem, we can check whether a given number is prime or not. For example, if 2^35 is not congruent to 2 modulo 35, then 35 is not prime.
I do not understand the 1-st speed up technique at 27;44.
31:47 Even if a^p = a (mod p) for any a, somtimes p is not a prime.
Carmichael number 561 is not prime and satisfies a^561 = a (mod 561) for any number a.
By the following three equations
a^561 = a (mod 3),
a^561 = a (mod 11),
a^561 = a (mod 17),
we get
a^561 = a (mod 3*11*17).
In fact, since 3,11,17 are coprime, a^561 - a = 3q = 11q’ = 17Q implies that a^561 -a = 3*11*17Q’.
38:11
Let p be a prime number.
LEMMA. If p divides n^2+1, then p = 2 in Z or p = 1 (mod 4).
PROOF
By the assumption, n^2 = -1 (mod p).
Because p is prime, p is odd.
By Fermat’s theorem, in Z/pZ, 1 = n^(p-1) = (-1)^( (p-1)/2 ) = -1 if (p-1)/2 is odd or 1 if (p-1)/2 is even (p = 1 mod 4). Note that 1 = -1 (mod p) occurs only in case of p =2. Thus, we proved the lemma.
Application of the above lemma.
The following corollary means that there are infinitely many primes congruent to 1 modulo 4.
COROLLARY. If p(1),…,p(k) are primes and all of them are congruent to 1 modulo 4 , then each prime factor of ( 2p(1)*…*p(k) )^2 + 1 is a new prime congruent to 1 modulo 4.
PROOF.
Consider prime factors q(1),..,q(n) of ( 2p(1)*…*p(k) )^2 + 1, that is,
( 2p(1)*…*p(k) )^2 + 1 is represented by powers of q(1),..,q(n).
Then the factors has the following properties.
1) Each of q(1),..,q(n) is congruent to 1 modulo 4 or equal to 2.
2) Each of q(1),..,q(n) is not equal to 2, p(1),…,p(k).
The first property follows from the above lemma, since each of prime q(i) divides ( 2p(1)*…*p(k) )^2 + 1 which has the form N^2 +1.
To show second property, e.g., suppose that q(1) = p(1), then p(1) divides ( 2p(1)*…*p(k) )^2 + 1 and hence p(1) divides 1, which is contradiction. Thus we proved.
STOP EXPAINING YOU'RE DUMB I KNOW IT YOU'RE JUST COPYING EVERYTHING HE SAID SO SHUT YOUR DIRTY MOUTH...
I didn't know that proof of Fermat's little theorem! I only knew the proof using Lagrange's theorem.
My favorite modulo trick uses the fact that 1001 = 7 * 11 * 13. We can use 1000 = -1 mod 1001 to check if very large integers are divisible by 7, 11 , and 13 all at once. e.g.
12,343,827 = 827 - 343 + 12 = 496 mod 1001
Now we have
12,343,827 = 496 = 6 mod 7
12,343,827 = 496 = 1 mod 11
12,343,827 = 496 = 2 mod 13
It's good to see that fields medalist contributing some of his time on undergraduate and senior ug lectures. Earlier some of your videos are difficult to understand and they assume some familiarity with those topics already before watching. But now with your increasing Playlist we can hope some serves as Playlist for your graduate lecture videos.
I'm surprised that Prof. Borcherds doesn't know about the Vedic divisibility rules. To test divisibility by 7 take the ones' digit multiplied by either (as a matter of convenience to the calculation) -2 or +5; and add it to the remaining digits shifted right one space. So one tests 343 by taking either -6 (as 3 * -2) or 15 (as 3 * +5) and adding it to 34 to get respectively 28 or 49: both of which are divisible by 7 confirming that 343 is also.
Unfortunately this doesn't readily preserve the modulus, though it can be regenerated from the cycle count.
This technique works for all divisors d, with the multiplier determined as ceiling of one tenth the smallest multiple of d with a ones digit of 9 (or that number minus d when subtraction is more convenient). Thus the multiplier for 13 is ceiling(39/10) = 4 (or -9) and that for 17 is ceiling(119/10) = 12 (or -5) , etc.
Note this gives a multipliers of -1 for 11 and +1 for 9, both equivalent to the traditional divisibility test for both of them.
The thumbnail says 'your text' on it :)
repeatedly adding up the digits checks for divisibility by 3
Thank you very much professor!
presumably congruence can be used anywhere else as well
pi is congruent to 0 sin
meaning
sin(pi) = 0
Let m,n be integers such that 4|m and n≡7(mod m). Show that n is not a perfect square.
yeeeeeeeeeeeeeeeeeeeeeeeeeee
I was waiting for his proof of Fermet's last theorem 😂