OJ Board

Posted: **Mon Jan 29, 2007 12:30 pm**

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

Posted: **Mon Jan 29, 2007 3:43 pm**

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

Hope this will help you!!!

DP

Posted: **Mon Jan 29, 2007 8:39 pm**

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

Posted: **Tue Jan 30, 2007 8:33 am**

Thanks for DP and Darko

.

Posted: **Tue Jan 30, 2007 10:17 am**

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?

Posted: **Tue Jan 30, 2007 2:42 pm**

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

Posted: **Wed Jan 31, 2007 4:58 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?

Posted: **Sat Feb 03, 2007 11:10 am**

Hm....

We can change the base also. So we will get x. But dont know, is it faster way!!!

Code: Select all

log 'a' base 'x' = log 'b' base 'x'/log 'b' base 'a'

Sorry for bad representation of log. I couldn't picturize it.

DP

OJ Board

Equation

Equation