Equation

Let's talk about algorithms!

Moderator: Board moderators

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

Equation

Post by 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
"Life is more beautiful with algorithm"

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Post by 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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by 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
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo »

Thanks for DP and Darko :D .
"Life is more beautiful with algorithm"

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by 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?
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
Location: Bangladesh
Contact:

Post by 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
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by 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?
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
Location: Bangladesh
Contact:

Post by DP »

Hm....:D
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

Post Reply

Return to “Algorithms”