Sorry, an error occurred while loading the content.
Browse Groups

• what is the best way to calculate x (via hand) for 1009 is factor of (x * 2333+ 577) 12 years ago I found a way to calculate it fast, but maybe it is not the
Jun 27 1 of 2
View Source
what is the best way to calculate x (via hand) for

1009 is factor of (x * 2333+ 577)

12 years ago I found a way to calculate it fast, but maybe it is not the
best way.

For larger ones like

6309163058327 is factor of ( x * 468126486184 + 687164871), I need maybe
<<50 steps.

Best and Thanks.
• On Thu, 6/27/13, Norman Luhn wrote: Subject: [PrimeNumbers] I have a question,please... To: primenumbers@yahoogroups.com
Jul 15 1 of 2
View Source
On Thu, 6/27/13, Norman Luhn <n.luhn@...> wrote:
"""
Subject: [PrimeNumbers] I have a question,please...
To: "primenumbers@yahoogroups.com" <primenumbers@yahoogroups.com>
Date: Thursday, June 27, 2013, 5:50 PM

what is the best way to calculate x
(via hand) for

1009 is factor of (x * 2333+ 577)

12 years ago I found a way to calculate it fast, but maybe
it is not the
best way.

For larger ones like

6309163058327 is factor of ( x * 468126486184 + 687164871),
I need maybe
<<50 steps.

Best and Thanks.
"""

1009 is factor of (x * 2333+ 577)
=>
x * 2333 + 577 == 0 (mod 1009)
=>
x * 2333 == -577 (mod 1009)
=>
x == -577 * (2333^-1) (mod 1009)

The calculation of the modular inverse can be done by nothing apart from addition and subtraction using the (extended) Euclidean algorithm, as it will give you a.s + b.t = 1, and when s=2333 and t=1009, that gives you 2333.a == 1 (mod 1009).

Phil
--
() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.