Math Puzzler

[maverick280857]

The problem:

Find the last digit of


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


The Answer: 1 (one)

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

Cheers
Vivek

[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

[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.

[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

[arildno]

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

[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

[arildno]

Oh, I hadn't thought of that! (Or, possibly I had..:wink:)

[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.

[maverick280857]

Yes it is, except that it is more formal.

Thanks and cheers,
Vivek

[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

[maverick280857]

Thanks faust9, Galileo, arildno and NateTG

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


Cheers
Vivek