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

## Equation

**Moderator:** Board moderators

Code: Select all

`1, (N+1), (2N+1), (3N+1), (4N+1), ................etc`

**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

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

Let,

Code: Select all

```
x^y=A.............(1)
(x+1)^y=B.......(2)
```

Code: Select all

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

Code: Select all

`ylog(x+1)=log(B)......(4)`

DP

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'
```

DP