# Thread: Some Math

1. ## Some Math

Hi ...can any one help me out with this

(A^N)%M can be calculated in O(log(N)) time using fast power modulo

but how do i calculate this ((A^N-1)/(A-1))%M ??
Note that the above formula if from a geometric series

Can any 1 help ?

thank u

2. If A-1 is invertible in Z mod M, then that's just one extra step since it can be written as a multiply. (I'm assuming here that A is an integer, otherwise the question makes no sense.)

If A-1 and M are not relatively prime, then no shortcuts for you.

3. ## Re

yes A is an integer , No it is no guarenteed that they are relatively prime
How do i solve this ???

4. Soooooooooooo, if you read, well, any of your book on discrete mathematics you would see something like

ad = bd (mod pd) iff a = b (mod p)

So since you need to divide by A-1, you need to do your initial congruence (i.e., in the calculation of A^n) not mod p, but mod p(A-1).

5. ## Re

Didn't quite get u ... the problem is i am not CS/IS student

Could u please explain a little more ?
ex:

((19^1015-1)/(19-1))%103 ..

how do i do this...

PYTHON gives 55 ans the answer..

Thank u

6. ## yay

Got it dude..
thank u so much !!

Popular pages Recent additions