# Some Math

• 09-12-2009
jack_carver
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
• 09-13-2009
tabstop
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-2009
jack_carver
Re
yes A is an integer , No it is no guarenteed that they are relatively prime
How do i solve this ???
• 09-13-2009
tabstop
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-2009
jack_carver
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
• 09-13-2009
jack_carver
yay
Got it dude..
thank u so much !!