Math Puzzler

1. Jul 25, 2004

maverick280857

The problem:

Find the last digit of

$$(1997)^{1997} - (1994)^{1994}$$

Will post a solution soon...I would like to know if there is a different way to do it.

Cheers
Vivek

Last edited: Jul 25, 2004
2. Jul 25, 2004

maverick280857

Solution 1: Find the last digit of $$m^{n}$$

Divide the exponent n by 4. Let n = 4p + q. Let the last digit of m be t. Then the last digit of $$m^{n}$$ is simply the last digit of $$t^{p}$$.

Do this twice to get 7 and 6 for $$(1997)^{1997}$$ and $$(1994)^{1994}$$ respectively. Subtract to get 1.

Solution 2: Find the last digit of $$m^{n}$$

Let a denote the last digit of m. Enumerate the last digits of $$a, a^{2}, a^{3}...$$ and denote this series by $$\lambda$$. The series clearly repeats after T terms where T is the period of the sequence. Note that

Let r be the remainder when n is divided by T. The remainder has the values (1, 2, 3, ..., (T-1), 0) [note that zero has been placed after the (T-1)th term so that $$\lambda_{T} = 0$$]. The answer then is the r-th term of the $$\lambda$$ sequence, that is $$\lambda_{r}$$.

------------------
What I want to know is: is there any other way to do this apart from the two ways mentioned above?

Cheers
Vivek

Last edited: Jul 25, 2004
3. Jul 25, 2004

faust9

4 to an even power will always have a last digit of 6.
if 7 is raised to a power of some number n where (n-1)%4=0 then the resulting last digit will be a 7.

1994 is even thus 6
(1997-1)%4=0 thus 7
7-6=1

basically the last digit will follow some pattern in this case, the powers of 4 flip flop between 4 and 6 while the powers of 7 rotate through 7,9,3,1.

4. Aug 3, 2004

maverick280857

Yes, instead of evolving general rules I found it quite enlightening to figure out the last digit without using the methods outlined in my second post :-D

Cheers
Vivek

5. Aug 3, 2004

arildno

Why didn't you just multiply out by hand and subtract?

6. Aug 3, 2004

maverick280857

Arildno, do you really think that would be possible?! Thats $$1997^{1997}$$ and $$1994^{1994}$$ we're talking about! It would take me days (if at all I managed to do it).

Cheers
Vivek

7. Aug 4, 2004

8. Aug 4, 2004

Galileo

Wer're only interested in the last digit of $1997^{1997}$ and $1994^{1994}$, so consider these numbers modulo 10.
$$1997^{1997} \equiv 7^{1997} \mod 10$$
$$1994^{1994} \equiv 4^{1994} \mod 10$$
Since $\left(\mathbb{Z}\slash_{10}\mathbb{Z}\right)^*$ forms a group under multiplication, raising an element of the group to the power equal to the order of the group equals 1. The order of $\left(\mathbb{Z}\slash_{10}\mathbb{Z}\right)^*$
is $\varphi(10)=\varphi(2)\varphi(5)=4$.
Since
$$1997 \equiv 1 \mod 4$$ and
$$1994 \equiv 2 \mod 4$$, we have
$$7^{1997} \equiv 7^1 \mod 10$$ and
$$4^{1994} \equiv 4^2 \mod 10$$

$$7-4^2 \equiv 1 \mod 10$$
So the last digit is 1.

This is the method I learned from my algebra class, but it's principally the same as Fausts' solution.

Last edited: Aug 4, 2004
9. Aug 4, 2004

maverick280857

Yes it is, except that it is more formal.

Thanks and cheers,
Vivek

10. Aug 4, 2004

NateTG

It's not that hard to exponentiate out, especially if you realize that you only care about the last digit:

$$1994=1024+512+256+128+8+2$$
and
$$1997=1024+512+256+128+8+4+1$$

Recognizing that we can throw away everything except the last digit:
$$7^1 \equiv 7$$
square to get
$$7^2 \equiv 9$$
square to get
$$7^4 \equiv 1$$
So $$7^{4n} \equiv 1$$
so we have
$$1997^{1997} \equiv$$
$$7 ^{1024+512+256+128+8+4+1} \equiv$$
$$7^{1024} \times 7^{512} \times 7^{256} \times 7^{128} \times 7^{8} \times 7^4 \times 7^1\equiv$$
$$1 \times 1 \times 1 \times 1 \times 1 \times 1 \times 7 \equiv$$
$$7$$

Similarly:
$$4^1 \equiv 4$$
$$4^2 \equiv 6$$
$$4^4 \equiv 6$$
So $$4^{2^n} \equiv 6$$ for $$n>1$$
now
$$1994^{1994} \equiv$$
$$4^{1024+512+256+128+8+2} \equiv$$
$$4^{1024} \times 4^{512} \times 4^{256} \times 4^{128} \times 4^{8} \times 4^2 \equiv$$
$$6 \times 6 \times 6 \times 6 \times 6 \times 6 \equiv$$
$$6^6 \equiv$$
$$6$$

Even without that $$x^y(mod z)$$ is $$O(\log_2(y) {\log_2(z)}^2)$$ or so. Certainly within paper and pencil calculation range for the numbers you gave

11. Aug 4, 2004

maverick280857

Thanks faust9, Galileo, arildno and NateTG

I learnt a lot from the approaches you folks suggested...thanks.

Cheers
Vivek