Math Puzzler

  • #1
1,789
4
The problem:

Find the last digit of

[tex]
(1997)^{1997} - (1994)^{1994}
[/tex]

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
 
Last edited:

Answers and Replies

  • #2
1,789
4
Solution 1: Find the last digit of [tex]m^{n}[/tex]

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

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

Solution 2: Find the last digit of [tex]m^{n}[/tex]

Let a denote the last digit of m. Enumerate the last digits of [tex]a, a^{2}, a^{3}...[/tex] and denote this series by [tex]\lambda[/tex]. 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 [tex]\lambda_{T} = 0[/tex]]. The answer then is the r-th term of the [tex]\lambda[/tex] sequence, that is [tex]\lambda_{r}[/tex].

------------------
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:
  • #3
691
1
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
1,789
4
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
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
134
Why didn't you just multiply out by hand and subtract?:confused:
 
  • #6
1,789
4
Arildno, do you really think that would be possible?! Thats [tex]1997^{1997}[/tex] and [tex]1994^{1994}[/tex] we're talking about! It would take me days (if at all I managed to do it).

Cheers
Vivek
 
  • #7
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
134
Oh, I hadn't thought of that! (Or, possibly I had..:wink:)
 
  • #8
Galileo
Science Advisor
Homework Helper
1,989
6
Wer're only interested in the last digit of [itex]1997^{1997}[/itex] and [itex]1994^{1994}[/itex], so consider these numbers modulo 10.
[tex]1997^{1997} \equiv 7^{1997} \mod 10[/tex]
[tex]1994^{1994} \equiv 4^{1994} \mod 10[/tex]
Since [itex]\left(\mathbb{Z}\slash_{10}\mathbb{Z}\right)^*[/itex] 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 [itex]\left(\mathbb{Z}\slash_{10}\mathbb{Z}\right)^*[/itex]
is [itex]\varphi(10)=\varphi(2)\varphi(5)=4[/itex].
Since
[tex]1997 \equiv 1 \mod 4[/tex] and
[tex]1994 \equiv 2 \mod 4[/tex], we have
[tex]7^{1997} \equiv 7^1 \mod 10[/tex] and
[tex]4^{1994} \equiv 4^2 \mod 10[/tex]

[tex]7-4^2 \equiv 1 \mod 10[/tex]
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:
  • #9
1,789
4
Yes it is, except that it is more formal.

Thanks and cheers,
Vivek
 
  • #10
NateTG
Science Advisor
Homework Helper
2,450
6
It's not that hard to exponentiate out, especially if you realize that you only care about the last digit:

[tex]1994=1024+512+256+128+8+2[/tex]
and
[tex]1997=1024+512+256+128+8+4+1[/tex]

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

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

Even without that [tex]x^y(mod z)[/tex] is [tex]O(\log_2(y) {\log_2(z)}^2)[/tex] or so. Certainly within paper and pencil calculation range for the numbers you gave
 
  • #11
1,789
4
Thanks faust9, Galileo, arildno and NateTG

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


Cheers
Vivek
 

Related Threads on Math Puzzler

  • Last Post
Replies
19
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
3
Views
1K
Replies
1
Views
1K
Replies
0
Views
1K
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
2
Views
646
  • Last Post
Replies
2
Views
1K
Top