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

Printable View

- 09-12-2009jack_carverSome 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 - 09-13-2009tabstop
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. - 09-13-2009jack_carverRe
yes A is an integer , No it is no guarenteed that they are relatively prime

How do i solve this ??? - 09-13-2009tabstop
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). - 09-13-2009jack_carverRe
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 - 09-13-2009jack_carveryay
Got it dude..

thank u so much !!