4 ms·
Is finding b such that (a * b) % n really that much work? It's (a % n + b % n) == 1. So pick b = a + 1 - a % n and you are done?
by omegalulw 5y ago
Is finding b such that (a * b) % n really that much work?
It's (a % n + b % n) == 1. So pick b = a + 1 - a % n and you are done?
- tzs 5y agoI think you are looking to find b such that a + b = 1 mod n. The problem is to find b such that a x b = 1 mod n. That only has a solution if a is relatively prime to n, and generally the best way to find that solution is to use the extended Euclidean algorithm [1]. Briefly because a and n are relatively prime, there exists integers x and y such that ax + ny = 1 [2]. The extended Euclidean algorithm finds x and y. But ax + ny mod n is just ax mod n, and so we have ax = 1 mod n. The b we seek is x. [1] https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm [2] https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity
- omegalulw 5y agoThanks! Reading my comment again it's clear I had a brain fart during writing the comment but I was indeed trying to solve: find b such that (a + b) % n == 1. Of course, assume a and n are relatively prime. Then this is equivalent to finding a b such that (a % n + b % n) % n == 1. We already know that 0 < a % n < n so simply picking b = n + 1 - a % n works. In fact, b = zn + 1 - a % n for any positive integer z works. Your solution makes sense to me too but I wonder if I'm missing something obvious above?
- omegalulw 5y agoSry, I had a brain fart again. My solution won't work, it's for a different problem. I can't delete comments from my phone and I think for the addition problem it's a reasonable solution so I'll just leave it.