What is the remainder if 7^10 is divided by 100?

BTGmoderatorDC wrote:What is the remainder if 7^10 is divided by 100?

A] 1
B] 43
C] 19
D] 70
E] 49
Source: Manhattan Prep

First note that:

> 1 is the remainder of 101 (=1*100+1) divided by 100
> 32 is the remainder of 532 (=5*100+32) divided by 100
> 47 is the remainder of 7847 (=78*100+47) divided by 100
$${7^{10}} = K \cdot 100 + R{\mkern 1mu} {\mkern 1mu} \,\,{\mkern 1mu} {\mkern 1mu} \left( {K\,\,{\mathop{\rm int}} \,\,,\,\,\,0 \le R \le 99\,\,{\mathop{\rm int}} } \right){\mkern 1mu} $$
$$? = R$$
$${7^{10}} = {\left( {{7^2}} \right)^5} = {49^5}$$
$${49^2} = {\left( {50 - 1} \right)^2} = {5^2} \cdot {10^2} - 100 + 1 = M \cdot 100 + 1\,\,\,,\,\,\,M\,\,{\mathop{\rm int}} \ge 1\,\,\,\,\,\,\,\,\,\,\left( {M = {5^2} - 1} \right)$$
$${49^4} = {\left( {M \cdot 100 + 1} \right)^2} = {M^2} \cdot {10^4} + M \cdot 200 + 1 = N \cdot 100 + 1\,\,\,,\,\,\,\,N\,\,{\mathop{\rm int}} \,\, \ge 1\,\,\,\,\,\,\,\,\left( {N = {M^2} \cdot {{10}^2} + 2M} \right)$$
$${49^5} = \left( {N \cdot 100 + 1} \right) \cdot 49 = K \cdot 100 + 49\,\,\,,\,\,\,\,K\,\,{\mathop{\rm int}} \,\, \ge 1\,\,\,\left( {K = 49N} \right)$$
$$? = 49$$

This solution follows the notations and rationale taught in the GMATH method.

Regards,
Fabio.

If we are asked to calculate the remainder when 6*5 is divided by 4, we observe that we can divide each of the numbers 6 and 5 and multiply their remainders to get the required answer.
For example , $$\frac{6}{4}$$ yields a remainder of 2 whereas $$\frac{5}{4}$$ gives 1.
Multiplying 2 and 1 is 2 - the same as the remainder when 30 is divided by 4.

We use this same principle in the above problem. We break the given product into small numbers whose remainder we can easily find. In this case we can write it as

$$7^9\cdot7$$ = $$343^3\cdot7$$
When 343 is divided by 100, the remainder is 43.
Our required answer is
(43*43)*(43*7)
=1849 * 301
The remainders when 1849 and 301 are divided by 100 are 49 and 1.
The product of 49 and 1 is 49 ... which is the required answer since 49 divided by 100 would continue to yield a remainder of 49.

BTGmoderatorDC wrote:What is the remainder if 7^10 is divided by 100?

A] 1
B] 43
C] 19
D] 70
E] 49

When a positive integer is divided by 100, the remainder is yielded by the last two digits:
123/100 = 1 R23
548/100 = 5 R48
692/100 = 6 R92

Thus:
The remainder when 7¹� is divided by 100 is equal to the last two digits of 7¹�.

Calculate the last two digits for consecutive powers of 7 and look for a pattern:
7¹ --> 07
7² --> 49
7³ --> 43
7� --> 01
7� --> 07

The last two digits appear in a CYCLE OF 4:
07, 49, 43, 01...07, 49, 43, 01...
Implication:
When 7 is raised to a power that is a MULTIPLE OF 4 -- constituting the end of a cycle -- the last two digits will be 01.
From there, the cycle will repeat:
07, 49, 43, 01...

Since 8 is a multiple of 4, the last two digits for 7� are 01.
The cycle then repeats:
7� ---> 07
7¹� --> 49

The correct answer is E.