Equation

[Timo]

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

[DP]

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

[Darko]

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]

Thanks for DP and Darko .

[ayon]

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?

[DP]

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]

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?

[DP]

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