He is awesome - not only in Maths but also as an inspiring teacher. Also his quality of chosen problems are genuinely challenging to solve, making them more fun to solve yourself.
The first time I saw your contents was some months ago and I liked it a bit, however, now I'm obsessed with it, you make the calcs in such a way that is impossible to dislike, also, the problems that you bring here are different from what we usually see at school. Thank you for what you've done with your videos.
I spent a whole year at university studying simple group theory and modular arithmetic. And for some reason, even when I saw the word "divisible", I still got into mathematical induction. But the strangest thing is that I was very surprised when we turned 30 into -1. There seems to be nothing so surprising, I have done this a thousand times in the ring modulo. Moreover, I have just now made sure that -1 is divided with a remainder by 31, the same as 30 is divided with a remainder by 31 (because by definition there are no sign restrictions on the divisible). And I was still surprised. It even became sad somehow, because I realized how limited I could be in a thing that I seemed to know well. (When you came to modules, I even remembered the definition of division with remainder completely!). Have where to grow! Cool video!
I did it fron the top of my head thanks to you!!! 30 = -1 mod 31 so 30^odd will be -1 mod 31. Then 5^21 = 125^7 and 125 = 1 mod 31. So added together it's -1 mod 31 +1 mod 31=0 mod 31
Very nice, really ! For those who don’t know (or don’t like) modular arithmetics, there is a quite fast solution…: Noticing that 5^21n = 125^7n, we have : 125^7n = (124 + 1)^7n = 31 X + 1 for an integer X, because in the binomial development of (124 + 1)^7n, all terms except 1^7n contain a power of 124 from 1 to 7n, and then contain 31. Same for 30^(10n + 1), we have : 30^(10n + 1) = (31 - 1)^(10n + 1) = 31 Y - 1 for an integer Y, because in the binomial development of (31 - 1)^(10n + 1), all terms except (- 1)^(10n + 1) contain a power of 31 from 1 to 10n + 1, and then contain 31. Then : 30^(10n + 1) + 5^21n = 31 Y - 1 + 31 X + 1 = 31 (X + Y). Thanks for your interesting videos 🙂
Waou! this is really amazing jpl569: simply by looking at binomial expression it becomes really simple to understand. I see this shortens 2 main explanations in the modular arithmetics (for a and b with respective rems r1 and r2, when multiplying them in the same modular we got r1*r2 as remainders (through binomial development easy to see this) and for additions/substraction the remainders are also added. Thx
Attempt: Lemma: A = B mod N implies for any arbitrary whole M, A^M = B^M mod N. A = B + NQ for some integer Q. A^M = (B + NQ)^M = B^M + Choose(M, 1) * B^(M-1) * NQ + Choose(M, 2) * B^(M-2) * N^2 * Q^2 * ... All terms after the B^M have a factor of N and are thus 0 mod N. = B^M QED Main proof: N is divisible by 31 is the same as N = 0 mod 31. For N = 0: 30^1 + 5^0 = 31 = 0 mod 31. Assume 30^(10k+1) + 5^(21k) = 0 mod 31. Then, in mod 31: 30^(10(k+1)+1) + 5^(21(k+1)) = 30^(10k+11) + 5^(21k+21) = 30^(10k+1) * 30^10 + 5^(21k) * 5^21 = 30^(10k+1) * (-1)^10 + 5^(21k) * (5^3)^7 (by lemma) = 30^(10k+1) * 1 + 5^(21k) * 125^7 = 30^(10k+1) + 5^(21k) * 1^7 (by lemma) = 30^(10k+1) + 5^(21k) * 1 = 30^(10k+1) + 5^(21k) = 0 QED
The problem involves proving that the expression 30^(10n+1) + 5^(21n) is divisible by 31 for any positive integer n. The easiest way to solve this problem is to use modular arithmetic, which involves working with the remainders of numbers when divided by a certain modulus. The key steps in the modular arithmetic approach are to express 30 and 5^21n in terms of their remainders when divided by 31, and then show that the sum of these remainders is always 0 modulo 31. The remainder of 30 when divided by 31 is -1, and the remainder of 5^21n when divided by 31 is 1, since 5^21 is congruent to 1 modulo 31. Combining these results, the expression 30^(10n+1) + 5^(21n) is always divisible by 31, as the sum of the remainders is always 0 modulo 31.
*Generally* (N-1)^(odd number) = -1 mod N AND (mN+1)^(any positive integer) = 1 mod N. If N = 31, then N-1 = 30 and if m = 4 then mN + 1 = 4 x 31 + 1 = 124 + 1 = 125, so 30^(odd number) = -1 mod 31 and 125^(any positive integer) = +1 mod 31. So, *Generally* 30^(2u+1) + 5^(3v) = -1 + 1 = 0 mod 31 for all positive integers u and v. In this problem, u = 5n = any multiple of 5 and v = 7n = any multiple of 7. Since u and v are still integers, so 30^(2 x 5n + 1) + 5^(3 x 7n) = -1 + 1 = 0 mod 31.
for any number n, it's expressed as kq + r for some k,q and remainder r. then, we say n is congruent to r (mod q). therefore, 10 is congruent to -1 (mod 11) because 10 = 1x11 - 1, where n = 10, k = 1, q = 11 and r = -1
This simplifies to solving for which n we get (-1)^(10n + 1) = -1 (mod 31). Multiplying both sides by -1 we get that we want to solve (-1)^(10n + 2) = 1 (mod 31). Since 10n + 2 is always even, this is always true.
now the question is, after u divide by 31 is the factor prime or is it divisible by something else? a totally different problem but still interesting 2 think about.
I accept everything you say as fact, but modular arithmetic is new to me. I would have appreciated a demonstration that 1^n mod 31 will always be 1 no matter what integer power n is.
He doesnt ever say 1=1^n mod 31. When I learnt modular maths we did the order different we just replaced the divide with mod and put the remainder after the = sign. For example: 10 mod 5 = 0 (10 / 5 has 0 remainder) 10 mod 4 = 2 (10 / 4 has 2 remainder) I found this much more intuitive compared to his way of writing it. 10 = 0 mod 5 10 = 2 mod 4 I think if you go over the video I think if you go over the video with what he wrote as 10 = remainder mod divisor it will make more sense I dont really like his way of writing it and in programming, how I learned, it is written as: numerator mod divisor = remainder.
30 is congruent to -1 mod 31, so (30)^(10.n +1) is congruent to (-1)^(10.n +1) mod 31, so it is congruent to -1 mod 31. (5)^(21.n) = (125)^(7.n). As 125 is congruent to 1 mod 31, then (5)^(21.n) is congruent to (1)^(7.n) mod 31, so it is congruent to 1 mod 31. Now the sum (30)^(10.n +1) + (5)^(21.n) is congruent to -1 + 1 = 0 mod 31, and the problem is finished.
Since 5^3 mod 31 is congruent to 1, 5^(3y*n) mod 31 is also going to be 1 no matter the y or n. But for 30^(x*n+1) mod 31 to be congruent to -1 x*n+1 needs to be an odd integer. therefor x*n needs to be an even integer. Which means x/n = 2k or n/x = 2k where k is and integer. Since multiplication is communitive we can assume without loss of generality that n>x and n/x = 2k --> n = 2kx --> x*n = 2kx^2, this shows that x needs to be a whole number or a fraction of a/sqrt(k) where a is an integer, otherwise 2kx^2 is not a whole even number. If these requirements are not met for x then 30^(x*n+1) mod 31 can be anything
Technically expressing remainder in negative is not correct. The only law which governs division is that remainder should be greater than or equal to zero and less than divisor. If it is not followed then the division can never arrive at certain decision as every one has their own way of defining remainder and quotient for ex 8 divided by 3 , I can say 2 as remainder and 2 as quotient but someone can say -1 as remainder and 3 is quotient which will make the divison indeterminate. So please refrain from saying we can go with negative remainders . Hope you will take it positively.
You're not understanding correctly the meaning of congruence, saying A≅B (mod n) doesn't necessarily means that if you divide A by n the remainder is B, it means that if you divide A by n and B by n you'll get the same remainder. Example: 14≅10 mod 4, because if you divide 14 by 4 and 10 by 4 you get a remainder of 2 in both cases.
MOST UNDERRATED MATH TEACHER
Exactly
He is awesome - not only in Maths but also as an inspiring teacher. Also his quality of chosen problems are genuinely challenging to solve, making them more fun to solve yourself.
The first time I saw your contents was some months ago and I liked it a bit, however, now I'm obsessed with it, you make the calcs in such a way that is impossible to dislike, also, the problems that you bring here are different from what we usually see at school. Thank you for what you've done with your videos.
Thank you!
i really want to learn about modular arithmetic. thanks for a such great introduction prime newtons!
You’re an amazing math teacher.
I spent a whole year at university studying simple group theory and modular arithmetic. And for some reason, even when I saw the word "divisible", I still got into mathematical induction. But the strangest thing is that I was very surprised when we turned 30 into -1. There seems to be nothing so surprising, I have done this a thousand times in the ring modulo. Moreover, I have just now made sure that -1 is divided with a remainder by 31, the same as 30 is divided with a remainder by 31 (because by definition there are no sign restrictions on the divisible). And I was still surprised. It even became sad somehow, because I realized how limited I could be in a thing that I seemed to know well. (When you came to modules, I even remembered the definition of division with remainder completely!).
Have where to grow! Cool video!
I think this happened because I only divided numbers that were greater than the divisor.
I come from C land, where there is only remainder operator and not modulo.
Thanks. Your videos are so relaxing
Would love to see a video of you proving the same by induction
I did it fron the top of my head thanks to you!!!
30 = -1 mod 31 so 30^odd will be -1 mod 31. Then 5^21 = 125^7 and 125 = 1 mod 31. So added together it's -1 mod 31 +1 mod 31=0 mod 31
Very nice, really !
For those who don’t know (or don’t like) modular arithmetics, there is a quite fast solution…:
Noticing that 5^21n = 125^7n, we have :
125^7n = (124 + 1)^7n = 31 X + 1 for an integer X, because in the binomial development of (124 + 1)^7n, all terms except 1^7n contain a power of 124 from 1 to 7n, and then contain 31.
Same for 30^(10n + 1), we have :
30^(10n + 1) = (31 - 1)^(10n + 1) = 31 Y - 1 for an integer Y, because in the binomial development of (31 - 1)^(10n + 1), all terms except (- 1)^(10n + 1) contain a power of 31 from 1 to 10n + 1, and then contain 31.
Then : 30^(10n + 1) + 5^21n = 31 Y - 1 + 31 X + 1 = 31 (X + Y).
Thanks for your interesting videos 🙂
Waou! this is really amazing jpl569: simply by looking at binomial expression it becomes really simple to understand. I see this shortens 2 main explanations in the modular arithmetics (for a and b with respective rems r1 and r2, when multiplying them in the same modular we got r1*r2 as remainders (through binomial development easy to see this) and for additions/substraction the remainders are also added. Thx
@@davez8816 Thanks to you... 🙂
You have exponents that need to be inside grouping symbols: 5^(21n), 125^(7n), etc.
@@robertveith6383 True, thanks !
Try that way but couldnt find the solution. Thx !
Superb explanation ....Thank you ...
Induction, binomial theorem did it for me, 30 = -1 (mod 31) and 5^3 = 1(mod 31) helped though.
Greetings from Brazil!
I like when he does his trademark reaction at 2:21
Attempt:
Lemma: A = B mod N implies for any arbitrary whole M, A^M = B^M mod N.
A = B + NQ for some integer Q.
A^M = (B + NQ)^M
= B^M + Choose(M, 1) * B^(M-1) * NQ + Choose(M, 2) * B^(M-2) * N^2 * Q^2 * ...
All terms after the B^M have a factor of N and are thus 0 mod N.
= B^M
QED
Main proof:
N is divisible by 31 is the same as N = 0 mod 31.
For N = 0: 30^1 + 5^0 = 31 = 0 mod 31.
Assume 30^(10k+1) + 5^(21k) = 0 mod 31.
Then, in mod 31:
30^(10(k+1)+1) + 5^(21(k+1))
= 30^(10k+11) + 5^(21k+21)
= 30^(10k+1) * 30^10 + 5^(21k) * 5^21
= 30^(10k+1) * (-1)^10 + 5^(21k) * (5^3)^7 (by lemma)
= 30^(10k+1) * 1 + 5^(21k) * 125^7
= 30^(10k+1) + 5^(21k) * 1^7 (by lemma)
= 30^(10k+1) + 5^(21k) * 1
= 30^(10k+1) + 5^(21k)
= 0
QED
Yes! Thank you! This lemma is essential to the proof, but he didn't explain it.
Easy way to solve. Thank you, sir. S Chitrai Kani
Thanks sir ♥️
The problem involves proving that the expression 30^(10n+1) + 5^(21n) is divisible by 31 for any positive integer n.
The easiest way to solve this problem is to use modular arithmetic, which involves working with the remainders of numbers when divided by a certain modulus.
The key steps in the modular arithmetic approach are to express 30 and 5^21n in terms of their remainders when divided by 31, and then show that the sum of these remainders is always 0 modulo 31.
The remainder of 30 when divided by 31 is -1, and the remainder of 5^21n when divided by 31 is 1, since 5^21 is congruent to 1 modulo 31.
Combining these results, the expression 30^(10n+1) + 5^(21n) is always divisible by 31, as the sum of the remainders is always 0 modulo 31.
Another possible approach could be to proceed via the principle of mathematical induction (PMI)
3^{10n+10n ➖}+{1n+1n ➖ }+105n=3^{20n^2+2n^2}+105n=3^22n^4={66n^4+105n}=171n^5 3^57n^5 3^19n^5 3^19^1n^5 3^1^1n^5 3^1n^5 3^1n^5^1 3^1n^1^1 3n^1 (n ➖ 3n+1).
Prove that 30^(10n+1)+5^(21n) is divisible by 31 I could use modular arithmetic.
*Generally* (N-1)^(odd number) = -1 mod N AND (mN+1)^(any positive integer) = 1 mod N.
If N = 31, then N-1 = 30 and if m = 4 then mN + 1 = 4 x 31 + 1 = 124 + 1 = 125, so 30^(odd number) = -1 mod 31 and 125^(any positive integer) = +1 mod 31.
So, *Generally* 30^(2u+1) + 5^(3v) = -1 + 1 = 0 mod 31 for all positive integers u and v.
In this problem, u = 5n = any multiple of 5 and v = 7n = any multiple of 7. Since u and v are still integers, so 30^(2 x 5n + 1) + 5^(3 x 7n) = -1 + 1 = 0 mod 31.
for any number n, it's expressed as kq + r for some k,q and remainder r. then,
we say n is congruent to r (mod q). therefore,
10 is congruent to -1 (mod 11) because 10 = 1x11 - 1, where n = 10, k = 1, q = 11 and r = -1
I simple logic in modular arithmetic can solve insanely complex problems if properly understood!
Excellent 👍❤
In modulo 31, the expression=(31-1)^(10n+1)+(5^3)^7n≡(-1)^(10n+1)+(31*4+1)^7n≡(-1)+(1)^7n≡0, since 31 divides 0, the proof is completed.
i loved it !
I find Newtons so relaxing to watch.
This simplifies to solving for which n we get (-1)^(10n + 1) = -1 (mod 31). Multiplying both sides by -1 we get that we want to solve (-1)^(10n + 2) = 1 (mod 31). Since 10n + 2 is always even, this is always true.
Modular arithmetic is very useful to solve divisibility problems. 👍
now the question is, after u divide by 31 is the factor prime or is it divisible by something else? a totally different problem but still interesting 2 think about.
I would have tried induction, because I am not that well versed in modulo arithmetic. And I'd still be trying to do it hours after you were done.
Nice trick!
I accept everything you say as fact, but modular arithmetic is new to me. I would have appreciated a demonstration that 1^n mod 31 will always be 1 no matter what integer power n is.
He doesnt ever say 1=1^n mod 31. When I learnt modular maths we did the order different we just replaced the divide with mod and put the remainder after the = sign. For example:
10 mod 5 = 0 (10 / 5 has 0 remainder)
10 mod 4 = 2 (10 / 4 has 2 remainder)
I found this much more intuitive compared to his way of writing it.
10 = 0 mod 5
10 = 2 mod 4
I think if you go over the video I think if you go over the video with what he wrote as 10 = remainder mod divisor it will make more sense I dont really like his way of writing it and in programming, how I learned, it is written as: numerator mod divisor = remainder.
Sir thumbnail kis application se banate ho
Cool thank you
Replace 30 with (31-1) and 5^3 with (4x31 + 1) … and then it follows almost immediately
30 is congruent to -1 mod 31, so (30)^(10.n +1) is congruent to (-1)^(10.n +1) mod 31, so it is congruent to -1 mod 31.
(5)^(21.n) = (125)^(7.n). As 125 is congruent to 1 mod 31, then (5)^(21.n) is congruent to (1)^(7.n) mod 31, so it is congruent to 1 mod 31.
Now the sum (30)^(10.n +1) + (5)^(21.n) is congruent to -1 + 1 = 0 mod 31, and the problem is finished.
Newtons is the equivalent of picasso but for maths.
🙏
8:43 it should be a congruent sign.
No. This is just rewriting the equation. You are not using modular arithmetic at this point.
However, at 09:03, it should be.
30 is congruent to -1 mod 31.
5^2=25 is congruent to -6 mod 31
Can't we solve this using Binomial Theorem???
lol, i was today yrs old when i learned that congruence equivalence symbol takes precedence over the arm.
looking back on this comment 3 months later i have no idea what i was talking about.
5 is congruent to 5 mod 31
10 is congruent to -1 mod 11.
10 is congruent to 2 mod 4.
10 mod 4 = 2
10 is congruent to 0 mod 2.
that's mean that all numbers written as 30^(x*n +1)+5^(3y*n) are divisible by 31 ? with x,y and n integers
Since 5^3 mod 31 is congruent to 1, 5^(3y*n) mod 31 is also going to be 1 no matter the y or n.
But for 30^(x*n+1) mod 31 to be congruent to -1 x*n+1 needs to be an odd integer. therefor x*n needs to be an even integer. Which means x/n = 2k or n/x = 2k where k is and integer. Since multiplication is communitive we can assume without loss of generality that n>x and n/x = 2k -->
n = 2kx --> x*n = 2kx^2, this shows that x needs to be a whole number or a fraction of a/sqrt(k) where a is an integer, otherwise 2kx^2 is not a whole even number.
If these requirements are not met for x then 30^(x*n+1) mod 31 can be anything
Jee level question
10 mod 2 = 0
Under 2hrs - - >
Technically expressing remainder in negative is not correct. The only law which governs division is that remainder should be greater than or equal to zero and less than divisor. If it is not followed then the division can never arrive at certain decision as every one has their own way of defining remainder and quotient for ex 8 divided by 3 , I can say 2 as remainder and 2 as quotient but someone can say -1 as remainder and 3 is quotient which will make the divison indeterminate. So please refrain from saying we can go with negative remainders . Hope you will take it positively.
You're not understanding correctly the meaning of congruence, saying A≅B (mod n) doesn't necessarily means that if you divide A by n the remainder is B, it means that if you divide A by n and B by n you'll get the same remainder. Example: 14≅10 mod 4, because if you divide 14 by 4 and 10 by 4 you get a remainder of 2 in both cases.
{n:X(n) | X/31}ℝ 𝕃 {x/31}ℝ
30^(10•1/31+1)+5^(21•1/31)
30^(10/31+1)+5^(21/31)=
30^1,3225 +5^0,677=89,84+2,973=92,813
92,813÷31=2,99 n=1/30,93
30^(1/30,93+1)+5^(21/30,93)=93,075
93,075÷31=3,00 n=1/30,93;
X=3,00 [proven successful]
10 is congruent to 1 mod 9.
10 is congruent to 10 mod 11.