What have you tried?
#Extended Euclidean Algo
modern stream
tired tulip
I tried basic algebra
Converting the LHS to mod 9527
Im not sure where to start here
28812 is 231 (mod9527)
modern stream
28812 is 231 (mod9527)
Okay, cool. Now you have to find the multiplicative inverse of 231 mod 9527.
tired tulip
Im not sure what to do
tired tulip
Okay, cool. Now you have to find the multiplicative inverse of `231` mod `9527`.
I got this far
9527 = 41(231) + 56
231 = 4(56) + 7
56 = 8(7) + 0
modern stream
I got this far
9527 = 41(231) + 56
231 = 4(56) + 7
56 = 8(7) + 0
Right. So there is no multiplicative inverse of 231 mod 9527 because they aren't coprime. They share a factor of 7. But: ak == bk (mod nk) -> a == b (mod n)
Therefore, we can divide everything by 7 to get 33x == 1 (mod 1361)
tired tulip
How is 28812 / 7 = 33
modern stream
How is 28812 / 7 = 33
...it's not. 231/7 = 33.
tired tulip
ohh
tired tulip
Right. So there is no multiplicative inverse of 231 mod 9527 because they aren't...
I dont understand this step
modern stream
I dont understand this step
Okay, look. By definition: a == b (mod n) <==> n|a - b <==> a - b = nk, k in Z
Right?
tired tulip
I don't understand that sorry
modern stream
I don't understand that sorry
<==> is a double-headed arrow, the symbol for biconditionality.
tired tulip
yes
tired tulip
I got this far
9527 = 41(231) + 56
231 = 4(56) + 7
56 = 8(7) + 0
In this equation, what are a,b,k,n defined as
modern stream
In this equation, what are a,b,k,n defined as
I was defining congruence mod n.
There are no "a,b,k,n" in "this equation" because 1) it's not an equation, and 2) it's not an instance of what I'm talking about.
tired tulip
But if you laid it out, what steps did you take to get to this "33x == 1 (mod 1361)"
modern stream
I was literally just trying to explain that, and you didn't get it.
tired tulip
Ok thanks for trying 👍
modern stream
Look. 33x * 7 == 1 * 7 (mod 1361 * 7), right?
modern stream
No!
Stop looking at your work and look at my work!
The only thing relevant about your work is that it spit out the shared factor of 7.
modern stream
...because what's 33 * 7?
tired tulip
231
modern stream
And what's 1 * 7?
tired tulip
7
modern stream
And what's 1361 * 7?
tired tulip
9527
modern stream
So...?
tired tulip
Oh I think I understand
modern stream
Thank God.
tired tulip
231 is 28812(mod 9527)
modern stream
...yes. We already knew that.
You realize we've spent most of the time we've been spending on this problem re-doing work we've already done?
tired tulip
Learning takes time
If you don't want to help me that's okay, thanks for what you taught so far tho
modern stream
That's fair, but at the same time it doesn't bode well for your mathematical career if you can't follow the trail of your own work.
Anyway.
33x * 7 == 1 * 7 (mod 1361 * 7), therefore 33x == 1 (mod 1361).
modern stream
Yes.
tired tulip
x = 1/33
modern stream
No.
This isn't equality, it's congruence. Only integers are allowed.
And I know you know that, because you knew what to do when I said to find a multiplicative inverse before.
tired tulip
So how do I solve for x?
modern stream
How do you think?
tired tulip
I don't know
modern stream
Think.
tired tulip
I dont know
tired tulip
I genuinely do not know
modern stream
I know you know what to do because you did it before.
tired tulip
Finding the multiplicative inverse?
modern stream
Yes.
tired tulip
of 33 mod 1361?
modern stream
Yes.
modern stream
idk what to do now
...distribute...
tepid ermine
+close