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.
I did it using congruence modulo, We know aΞ0(mod a) using this property, 31Ξ0(mod 31) 31 = 30 + 1 30 Ξ -1(mod 31) 30^(10n+1) Ξ -1(mod 31) Since 10n+1 is odd Now, 5³ = 125 when divided by 31 it gives remainder 1. 5³ Ξ 1(mod 31) (5³)⁷ Ξ 1⁷(mod 31) 5^(21n)Ξ1(mod 31 ) We know another property a Ξ n (mod m) and b Ξ c(mod m) then this implies (a+b) Ξ (n+c) (mod m) Therefore, 30^(10n+1) + 5^(21n)Ξ0(mod 31) Hence, 31 | 30^(10n+1) + 5^(21n) This proves 30^(10n+1) + 5^(21n) divisible by 31. [Note:-Sir I solved the problem before starting the video]. Sir,let me know if I did the right approach and my steps were correct or not as I am doing congruence modulo in my classes.
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.
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 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!
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
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!
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 !
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.
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.
Thanks sir ♥️
I like when he does his trademark reaction at 2:21
*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.
I did it using congruence modulo,
We know aΞ0(mod a) using this property,
31Ξ0(mod 31)
31 = 30 + 1
30 Ξ -1(mod 31)
30^(10n+1) Ξ -1(mod 31)
Since 10n+1 is odd
Now, 5³ = 125 when divided by 31 it gives remainder 1.
5³ Ξ 1(mod 31)
(5³)⁷ Ξ 1⁷(mod 31)
5^(21n)Ξ1(mod 31 )
We know another property a Ξ n (mod m) and b Ξ c(mod m) then this implies (a+b) Ξ (n+c) (mod m)
Therefore, 30^(10n+1) + 5^(21n)Ξ0(mod 31)
Hence, 31 | 30^(10n+1) + 5^(21n)
This proves 30^(10n+1) + 5^(21n) divisible by 31.
[Note:-Sir I solved the problem before starting the video].
Sir,let me know if I did the right approach and my steps were correct or not as I am doing congruence modulo in my classes.
Correct!
@@PrimeNewtons Thank you Sir.🙏🙏
@@PrimeNewtons
No reply
Just ignore
Like most TH-camr
👎🏼👎🏼👎🏼
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).
Sir thumbnail kis application se banate ho
Prove that 30^(10n+1)+5^(21n) is divisible by 31 I could use modular arithmetic.
Excellent 👍❤
Modular arithmetic is very useful to solve divisibility problems. 👍
I find Newtons so relaxing to watch.
i loved it !
Nice trick!
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.
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.
I simple logic in modular arithmetic can solve insanely complex problems if properly understood!
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.
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
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.
Cool thank you
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.
10 is congruent to 2 mod 4.
Can't we solve this using Binomial Theorem???
30 is congruent to -1 mod 31.
5 is congruent to 5 mod 31
Replace 30 with (31-1) and 5^3 with (4x31 + 1) … and then it follows almost immediately
10 is congruent to -1 mod 11.
5^2=25 is congruent to -6 mod 31
10 mod 4 = 2
10 is congruent to 0 mod 2.
Jee level question
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
lol, i was today yrs old when i learned that congruence equivalence symbol takes precedence over the arm.
10 mod 2 = 0
Newtons is the equivalent of picasso but for maths.
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.