232 reputation
38
bio website
location
age
visits member for 2 years, 10 months
seen Oct 1 at 13:52

Sep
14
awarded  Notable Question
Nov
1
awarded  Popular Question
Jun
23
awarded  Notable Question
May
18
comment Doing modular division when denominator and modulus not coprime
So even if I only have n mod m, I should be able to do (n mod m)/g?
May
18
comment Doing modular division when denominator and modulus not coprime
How do I find g if I only have n mod m and d?
May
18
comment Doing modular division when denominator and modulus not coprime
@anon It was a useless thought, I was thinking that if the moduli were prime then they'd for sure be coprime to the denominators but that's false
May
18
comment Doing modular division when denominator and modulus not coprime
I don't have the full n necessarily so I don't think I can reliably verify that g divides n
May
18
comment Doing modular division when denominator and modulus not coprime
@anon what if I use chinese remainder theorem to break up the modulus into prime powers?
May
18
comment Doing modular division when denominator and modulus not coprime
@anon No I mean if I have n mod m, and d (no mod), wanting to find n / d mod m
May
18
comment Doing modular division when denominator and modulus not coprime
What if I have d in full?
May
18
comment Doing modular division when denominator and modulus not coprime
And again please assume I do not have n and d in full. I am trying to find the answer assuming n and d have already been reduced. Sometimes it isn't possible to have them in full form because I can only calculate them modulo m (for example a very large modular exponent)
May
18
comment Doing modular division when denominator and modulus not coprime
Please note below when I said "it takes parameters n, d, and m, and assumes that n/d results in a whole number (without applying any modulus)"
May
18
comment Doing modular division when denominator and modulus not coprime
I wouldn't call the modular division function on those types of numerators and denominators. My function is meant for n and d such that n % d = 0, or when d divides n
May
18
comment Doing modular division when denominator and modulus not coprime
@anon I feel like we are talking past each other. It does make sense because every single n/d results in a whole number that I can then apply modulo m to. You can take any integer and apply modulo m to it. For example I can do 100/4 modulo 10 which gives me 5. So now let's say I have n= 100 mod 10 = 0 and d = 4 mod 10 = 4. I now want to somehow get 5, only armed with n=0, d=4, and m=10. I can't do (0*inverse(4,10)) mod 10
May
18
comment Doing modular division when denominator and modulus not coprime
@anon I don't understand how it applies to what I am trying to do. I have n mod m. I have d mod m. I want to return the same number I would have gotten had I done n / d then modulo m at the end.
May
18
comment Doing modular division when denominator and modulus not coprime
@anon I don't understand the answer. All I know is that I can compute a bunch of n/d's directly and apply mod m at the very end, and get some result X mod m. But then when I try to do a bunch of n mod m times inverse(d,m) mod m's, I do not get X mod m. Sometimes gcd(d,m) is 1 and sometimes it isn't, so I assume this is why my results differ.
May
18
comment Doing modular division when denominator and modulus not coprime
@anon I added a comment in the answer below to explain more specifically what I am doing
May
18
comment Doing modular division when denominator and modulus not coprime
I am writing a function to handle generalized modular division, it takes parameters n, d, and m, and assumes that n/d results in a whole number (without applying any modulus). That being said, when gcd(d,m)=1 there is no issue just returning n*inverse(d,m) but when gcd(d,m) is not 1, I'm stuck
May
18
comment Doing modular division when denominator and modulus not coprime
What is s and t?
May
18
comment Doing modular division when denominator and modulus not coprime
I'm not sure this helps me, technically. I have n and d, which are both modulo m. I don't have their full forms pre-modulus. Am I stuck then?