## Equation

Moderator: Board moderators

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

### Equation

I only know the value of A and N, how to solve this equation:

(A^X) % N == 1

I must compute the value of X.
(2<=A,N<=1000000000).

Thanks

Timo
"Life is more beautiful with algorithm"

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Contact:
If remainder is always 1 then i think the sequence will be :

Code: Select all

``1, (N+1), (2N+1), (3N+1), (4N+1), ................etc``
So, try to think now about logarithm.

Let, c={0,1,2,3,4,.....m}
Then, we got the following thing:

Code: Select all

``(cN+1)%N=A^x%N``

DP

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
http://mathworld.wolfram.com/EulersTotientTheorem.html

Note that it works only if A and N are relatively prime. If they are not, you will have to use
http://mathworld.wolfram.com/ChineseRem ... eorem.html

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia
Thanks for DP and Darko .
"Life is more beautiful with algorithm"

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
say i have A, B, i have to determine x and y from the two equations:

x^y = A;
(x+1)^y = B

what should be the best approach?
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Contact:
OK.
Let,

Code: Select all

``````x^y=A.............(1)
(x+1)^y=B.......(2)``````
Then, take logarithm in both sides of eqn. (1), so we got,

Code: Select all

``````ylog(x)=log(A)
y=log(A)/log(x).......(3)``````
Similarly,

Code: Select all

``ylog(x+1)=log(B)......(4)``
Finally replace y in eqn.(4). You will get x. After that y.

DP

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
thanks to DP, but it goes to something like

log(1+x) /log(x) = fractional_constant

now how to get x? there are several methods, but what should be best?
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
``````log 'a' base 'x' = log 'b' base 'x'/log 'b' base 'a'