Algebra Solutions: Compute large powers in ZZ/(n)

Compute large powers in ZZ/(n)

Compute the last two digits of $9^{1500}$ .

What we need to find is the residue class of $9^1500$ mod 100. Note first that, mod 100, we have the following.

$9^{100}$	=	$(9^2)^2 \cdot ((((9^2)^2)^2)^2)^2 \cdot (((((9^2)^2)^2)^2)^2)^2$
	=	$81^2 \cdot (((81^2)^2)^2)^2 \cdot ((((81^2)^2)^2)^2)^2$
	=	$61 \cdot ((61^2)^2)^2 \cdot (((61^2)^2)^2)^2$
	=	$61 \cdot (21^2)^2 \cdot ((21^2)^2)^2$
	=	$61 \cdot 41^2 \cdot (41^2)^2$
	=	$61 \cdot 81 \cdot 81^2$
	=	$61 \cdot 81 \cdot 61$
	=	$1$ .

Thus $9^{1500} = (9^{100})^{15} = 1^{15} = 1$ , and the last two digits of $9^{1500}$ are 01.

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)