I have a question about finding remainders from division

Question

If I have the following number, called n: 95789475894946344480971579557266277535799700804994840267140205584908768904895768948590485961900214653419480471608575222628934671405734092147743953303897316683406873623402076894361066482026698747269194533568241380908198579649362123303511284937304748452871420978357485793030284954802940809309474904948944096953

and this n is, firstly, going to be multiplied z many times and, secondly, z x n is divided by the following divisor: 258732191050391204174482508661063007579358463444809715795726627753579970080749948404278643259568101132671402056190021464753419480472816840646168575222628934671405739213477439533870489791038973166834068736234020361664820266987726919453356824138007381985796493621233035112849373047484148339095287142097834798153

and, thirdly, I know that the remainder I am seeking is the following number: 5789475894946344480971579572662775758908698579584974935799700804994840427864325956810113267140205584908768904895768948590485961900214653419480471608575222628934671405734092147743953387048979103897316683406873623465789384057098302076894361664820266987472691945335682413809081985796493303511284937304748414539

and fourthly, n and the divisor are co-prime,

Then what is z?

If the largeness of the numbers is confusing then let me just example what I am seeking to ask with smaller numbers:

If I have the number 73 and firstly, this 73 is going multiplied z many times and then, secondly, z x 73 is going to be divided by 97 and, thirdly, I know that the remainder form this division is 56, and fourthly, n=73 and divisor=97 are co-prime. then what is z?

The answer is 30. To verify:

73 x 30 = 2190 and 2190 mod 97 = 56.

I can just calculate multiples of 73 from 1 to 96 and write each product in a computer spreadsheet cell in succeeding rows and then at each row the product is divided by 97. At the 30th row I will see that the remainder is 56. It is easy because the numbers are small.

I can't count up to rows to a value that is over 300 digits long. Even in a thousand years I won't get the answer this way, even if I had a super-computer.

So ultimately the question is: What algorithm can I use to reduce the search time down to under 1 minute?

I do know that for other things such as large modular multiplicative inverses, even when the numbers are over 300 digits, the modular inverse can be found in less than 3 seconds using the Extended Euclidean algorithm using a standard desktop home computer that has a i3 intel microchip processor. So, Is there something like the Extended Euclidean algorithm that I can use to find the z multiple of number n when working with very large integers?

Teach me. I want to learn it.

Answer 1

Let's say you have the modulus $m$, the number $n$ and the remainder $r$ - you are looking for $z$ such that $nz\equiv r\pmod m$. You have also given us that $\gcd(n,m)=1$

What you need to do is: (a) First find the multiplicative inverse of $n\pmod m$. Let's call it $n^{-1}$. You will have $nn^{-1}\equiv 1\pmod m$. (b) Take $z\equiv n^{-1}r\pmod m$. You will have $nz\equiv nn^{-1}r\equiv 1\cdot r=r\pmod m$.

For the step (a), use the extended Euclidean algorithm.

---

In your example, $n=73, d=97, r=56$. The multiplicative inverse of $73\pmod{97}$ is $4$, so you are looking for $z=4\cdot 56=224\equiv 30\pmod{97}$.

---

For the motivation, note that what you are asking to do is solve the equation $nz=r$ in some ring ($\mathbb Z/m\mathbb Z$). If it was a different ring ($\mathbb Q$) you would immediately say $z=\frac{r}{n}=n^{-1}r$. What I am saying here is: the same logic works in any commutative ring with unity, as long as $n$ has an inverse, which due to the condition $\gcd(n,m)=1$ is true.