Another way to do it might be : break 143 into 11 and 13 then 34inv(mod 143) => 34 inv (mod 11) and 34 inv (mod 13) 34 inv (mod 11) and 8 inv (mod 13) then apply the chinese remainder theorem to get the required x(modulo 143). Hope it helps!
Note that the prime factorisation of 20 is 2^2 * 5, and the prime factorisation of 10 is 2*5. Therefore, the inverse pairs of 20 is the set of the inverse pairs of 10 (which are especially easy to calculate when taking 9==-1 (mod 10)) + the same set +10. ie { {1,1} , {3,7} , {9,9} } u { {11,11} , {13,17} , {19,19} }.
9:15 I am confused plz help me to understand why the hell we are doing 143 -21 = 122 ? whats the reason ? whats the logic ? whats the in-depth reason ?
The modulus looks at remainders. Specifically we're looking for the remainders when dividing by 143. The possible remainders are: 0,1,2,3,...,141,142. The value -21 is not in this set. To find the proper congruence class, we add 143 to -21 to get -21+143 = 143-21 = 122. Therefore, -21 = 122 (mod 143). Both -21 and 122 produce the same remainder when dividing over 143. If you're still confused why this works, consider a simpler example such as -2 = 10 (mod 12). Think of numbers on a clock. 2 hours before noon is 10 AM and notice how -2+12 = 10.
Much easier way. (he wanted multiplicative inverse 9f 34 mod 143. No problem. First, find the continued fraction representation of 34/143. It's [4, 4, 1, 6]. Underneath we put in the convergents, = [1/4, 4/17, 5/24, 34/143]. From the rightmost denominator (143), subtract the denominator to the left (24), getting the answer (122). The rule is that if there's an even number of partial quotients (four in this case, [4, 4, 1 ,6 ] perform the denominator subtraction procedure. But if the number of partial quotients is odd, just take the denominator to the left of rightmost denominator.. Example. multiplicative inverse of 5 mod 21. Data: [4, 4, 1], with convergents [1/4, 4/17, 5/21] Denominator to left of 21 = 17. That's the answer since 5 * 17 = 85 = 1 mod 21.
Démonstration. Soit le développement en fractions continues de la fraction a/b (a et b premiers entre eux). Soient p_n/q_n les réduites. D'après les résultats classiques sur les développements en fractions continues : D'une part les déterminants d'ordre 2 |q_(n-2) p_(n-2)| |q_(n-1) p_(n-1)| sont alternativement égaux à 1 et à -1. D'autre part, le dernier couple (q_n, p_n) est (q_N, p_N)=(b, a). On a donc : |q_(N-1) p_(N-1)| |b a| = (-1)^N (où N est la longueur du développement en fractions continues). Si l'on plonge ce déterminant dans Z/aZ, on voit que p_(N-1), est l'inverse ou l'opposé de l'inverse de b. (a étant le modulo. Dans l'exemple de @yifuxero9745, ce n'est pas p_(N-1), numérateur, mais q_(N-1), dénominateur, car c'est b le modulo).
@@dassive_mick4271 6 = 34 - 4 * (143 - 4 * 34) 6 = 34 - 143 * 4 + 16 * 34 Because 34 is used as an expression, we combined 34 with 16 * 34. Hence we get 17 * 34: 6 = -143 * 4 + 17 * 34 or how its formatted in the video: 6 = 17 * 34 - 4 * 143
First step is to write out the continued fraction representation CF of the fraction 34/143. It's [4, 4, 1, 6]. Write the remainders under those terms, which are [1/4, 4/17, 5/21, and 34/143]. There's your 17, denominator of 4/17.. Use the CF method to get the answer. From the rightmost denominator (143), subtract the denominator to it's left, (34), giving 122, the answer.
Well all of that is alright, I had my number theory class yesterday (I am a math olympiad student) and my teacher taught me this. To me this seemed very trivial and I am still not sure how is it useful. He even stressed the word 'powerful technique' during his lectures. If anyone knows how, please do share
I have been struggling with number theory and your channel by far the most helpful to me. Thank you!
Another way to do it might be :
break 143 into 11 and 13
then 34inv(mod 143) =>
34 inv (mod 11) and 34 inv (mod 13)
34 inv (mod 11) and 8 inv (mod 13)
then apply the chinese remainder theorem to get
the required x(modulo 143).
Hope it helps!
Professor Penn, thank you for another step by step explanation of the Modulo Inverses.
Modulo? More like way-to-go! Thanks again for another wonderful demonstration.
Sir i am very thankful to God that i get teacher like you.
Note that the prime factorisation of 20 is 2^2 * 5, and the prime factorisation of 10 is 2*5. Therefore, the inverse pairs of 20 is the set of the inverse pairs of 10 (which are especially easy to calculate when taking 9==-1 (mod 10)) + the same set +10. ie { {1,1} , {3,7} , {9,9} } u { {11,11} , {13,17} , {19,19} }.
My man! so helpful.
9:15
I am confused plz help me to understand
why the hell we are doing 143 -21 = 122 ?
whats the reason ? whats the logic ?
whats the in-depth reason ?
The modulus looks at remainders. Specifically we're looking for the remainders when dividing by 143. The possible remainders are: 0,1,2,3,...,141,142. The value -21 is not in this set. To find the proper congruence class, we add 143 to -21 to get -21+143 = 143-21 = 122. Therefore, -21 = 122 (mod 143). Both -21 and 122 produce the same remainder when dividing over 143.
If you're still confused why this works, consider a simpler example such as -2 = 10 (mod 12). Think of numbers on a clock. 2 hours before noon is 10 AM and notice how -2+12 = 10.
thanks brother for trying to solve my confusion. I will brainstorm into the simpler example. thanks again@@jimthompson5910
Much easier way. (he wanted multiplicative inverse 9f 34 mod 143. No problem. First, find the continued fraction representation of 34/143. It's [4, 4, 1, 6]. Underneath we put in the convergents, = [1/4, 4/17, 5/24, 34/143]. From the rightmost denominator (143), subtract the denominator to the left (24), getting the answer (122). The rule is that if there's an even number of partial quotients (four in this case, [4, 4, 1 ,6 ] perform the denominator subtraction procedure. But if the number of partial quotients is odd, just take the denominator to the left of rightmost denominator.. Example. multiplicative inverse of 5 mod 21. Data: [4, 4, 1], with convergents [1/4, 4/17, 5/21] Denominator to left of 21 = 17. That's the answer since 5 * 17 = 85 = 1 mod 21.
Démonstration.
Soit le développement en fractions continues de la fraction a/b (a et b premiers entre eux).
Soient p_n/q_n les réduites.
D'après les résultats classiques sur les développements en fractions continues :
D'une part les déterminants d'ordre 2
|q_(n-2) p_(n-2)|
|q_(n-1) p_(n-1)|
sont alternativement égaux à 1 et à -1.
D'autre part, le dernier couple (q_n, p_n) est (q_N, p_N)=(b, a).
On a donc :
|q_(N-1) p_(N-1)|
|b a|
= (-1)^N (où N est la longueur du développement en fractions continues).
Si l'on plonge ce déterminant dans Z/aZ, on voit que p_(N-1), est l'inverse ou l'opposé de l'inverse de b.
(a étant le modulo. Dans l'exemple de @yifuxero9745, ce n'est pas p_(N-1), numérateur, mais q_(N-1), dénominateur, car c'est b le modulo).
At 7:47 how did you get 17
6=34-4.(143-4.34)
@@gmcflyer what do u mean
@@dassive_mick4271
6 = 34 - 4 * (143 - 4 * 34)
6 = 34 - 143 * 4 + 16 * 34
Because 34 is used as an expression, we combined 34 with 16 * 34.
Hence we get 17 * 34:
6 = -143 * 4 + 17 * 34
or how its formatted in the video:
6 = 17 * 34 - 4 * 143
First step is to write out the continued fraction representation CF of the fraction 34/143. It's [4, 4, 1, 6]. Write the remainders under those terms, which are [1/4, 4/17, 5/21, and 34/143]. There's your 17, denominator of 4/17.. Use the CF method to get the answer. From the rightmost denominator (143), subtract the denominator to it's left, (34), giving 122, the answer.
thanks so much
good teacher
😮
✅
With the mod 20, you forgot the pairs {3, 17} and {7, 13}
you forget the mod : here it s 20 so 51 and 91 can t be 1 more than a multiplication of any number by 20
Well all of that is alright, I had my number theory class yesterday (I am a math olympiad student) and my teacher taught me this. To me this seemed very trivial and I am still not sure how is it useful. He even stressed the word 'powerful technique' during his lectures.
If anyone knows how, please do share
Who teaches you for olympiads??
@@TechToppers I am at cheenta
@@ramakrishnasen4386
That's good. It has nice staff I think...
@@ramakrishnasen4386 could I get your telegram id.I wanna know about cheenta like what kind of course structure is There