Hi,
I am trying to calculate:

99^7 (mod 123) = 93,206,534,790,699 mod 123 = 93,206,534,790,699- 757,776,705,615 * 123
93,206,534,790,699 - 93,206,534,790,645 44= 45

However, when I am doing it by breaking it into small powers I am getting wrong results like:

= [(99 mod 123) * (99 ^2 mod 123) * (99^4 mod 123)] mod 123

= [24* 75 * 75 * 75] mod 123 = 10,125,000 mod 123 = 82,317 * 123= 10,125,000-10,124,991=9

Somebody please guide me what is the problem.

Zulfi.

 

I've added some comments to your post:



I get these results in carrying out your calculations:

 

Hi,
Thanks for catching my subtraction error.
I think your last two answers should be same: your last answer is: 9 and before the last one you are getting :54?

Why there are two different answers for same calculation?

This is the problem I am getting too?
Please guide me

Zulfi.

 

You didn't answer my question about where 24*75*75*75 came from.

 

Edit : wow : was trying latex but screwed up ..Point is this : use math to solve your question and use chinese remainder theorem (guess it's the name)

Hi..Sorry to divert : did not follow calculation
but why don't you do easy way? why long multiplication?

123 = 3 * 41 ?

99^7 = 3*x so 99^7 is 0mod3

99 = 2*41 +17

so 99^7 mod 41 = 17^7 mod 41

17^2 mod41 = 2mod41

so 17^7mod41 = 8*17 mod41 = 13mod41

so :

99^7 = 3x and 99^7 = 41y + 13

3x = 41y + 13
x = 13y + 4 + (2y + 1)/3

y = z + (z - 1)/2

z = 2k + 1
y = 3k + 1

3x = 99^7 = 41(3k + 1) + 13

99^7 = 123k + 54