This is a homework question.
I need to calculate 45^60 mod 61. I want to know of any fast method to get the result either programmatically or manually whichever is faster.
Asked
Active
Viewed 831 times
3
-
programmatically will be faster i think. you can use C POW function and % operator to get the job done. – Tobias Mar 18 '11 at 05:58
-
1manually? you don't have to write any code? then ask wolfram alpha http://www.wolframalpha.com/input/?i=45^60+mod+61 – mpen Mar 18 '11 at 06:07
-
1@Tobias: that definitely will not work. 45^60 has somewhere around 320 bits, a lot more than any `double` or even `long double`. – R.. GitHub STOP HELPING ICE Mar 18 '11 at 13:04
-
[Calculating pow(a,b) mod n](http://stackoverflow.com/q/8496182/995714) – phuclv Sep 06 '15 at 05:19
5 Answers
21
The result would be 1 because of Fermat's little theorem
if p is prime.
61 is a prime number so ap-1 when divided by p would give 1 as the remainder.
However if p is non-prime the usual trick is repeated-squaring.
Prasoon Saurav
- 88,492
- 46
- 234
- 343
-
1+1, but `a is an integer coprime to p` should follow after if p is prime. – Sanjeevakumar Hiremath Mar 18 '11 at 19:54
-
There are also other theorems than can be used for speeding `a^b mod p` when p is not prime and b is big. – ypercubeᵀᴹ Mar 21 '11 at 00:39
6
45^60 =
2025^30 = (33*61 + 12)^30 = 12^30 =
144^15 = (2*61 + 22)^15 = 22^15 =
10648^5 = ( 174*61 + 34)^5 = 34^5 =
45435424 = 744843 * 61 + 1 = 1
Here equality means = (mod 61)
Markus Jarderot
- 83,508
- 19
- 134
- 137
MKo
- 4,438
- 8
- 30
- 34
4
I would say your best bet would be to use Fermat's Little Theorem.
where p = 61 and p-1 = 60.
Hope that helps
Chris McKnight
- 8,430
- 4
- 27
- 30
1
45^2 = 2025 = 12
45^4 = 12^2 = 144 = 22
45^8 = 22^2 = 484 = 57
45^16 = 57^2 = 3249 = 16
45^32 = 16^2 = 256 = 12
45^60 = 45^(4+8+16+32) = 22 * 57 * 16 * 12 = 1
aaz
- 5,016
- 21
- 16
