Exponentiation mod n

Sometimes it can be hard to obtain information about large numbers because of the complexity of multiplication and division. For example 67¹¹ is the 21 digit number 122130132904968017083 which can't be held accurately in a handheld calculator. If you wanted to determine whether 41 divided this number you would probably have to attempt this by long division. However, modular arithmetic offers a neat way round these problems.

Firstly we determine the remainder when 67 is divided by 41. We find that 67=1x41+26 and so the remainder is 26 and so we can write 67≡26 (mod 41). Now the neat trick of modular arithmetic is that the remainder on dividing 67¹¹ by 41 is the same as the remainder on dividing 26¹¹ by 41. However, rather than doing this in one go, we do it in bite-size chunks using repeated squaring to make the maths easier. So,  67²≡26² (mod 41) and since 26² is 676 and 676=16x41+20 then 67²≡20 (mod 41). Carrying on in a similar vein we have (67²)²=67⁴≡20² (mod 41) and as 20²=400=9x41+31 then 67⁴≡31 (mod 41). Further (67⁴)²=67⁸≡31² (mod 41) and as 31²=961=23x41+18 then 67⁸≡18 (mod 41).

Squaring any further doesn't help us as the index becomes 2x8=16 which is greater than 11. However as 67¹¹=67⁸x67³ we can continue by working out the remainder when 67³ is divided by 41 and multiplying this by the remainder when 67⁸ is divided by 41, which we have just worked out. Previously we saw that 67²≡20 (mod 41) and 67≡26 (mod 41) and so 67³=67²x67≡20x26 (mod 41). Now 20x26=520=12x41+28 and so 67³≡28 (mod 41). Hence 67¹¹≡18x28=504≡12 (mod 41) since 504=12x41+12.

Thus in answer to our original question 41 doesn't divide 122130132904968017083 as it leaves remainder 12.

This process of reducing a large division into a series of smaller steps using modular arithmetic lends itself well to computation on a programmable calculator. In particular, reducing the index by successive applications of repeated squaring is a fast way to obtain the remainder when a number can be expressed as a number raised to some power.