# I have a question about finding remainders from division

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.

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$$.
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.