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
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
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.
yes A is an integer , No it is no guarenteed that they are relatively prime
How do i solve this ???
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).
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
Got it dude..
thank u so much !!
