Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Math Puzzler

  1. Jul 25, 2004 #1
    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: Jul 25, 2004
  2. jcsd
  3. Jul 25, 2004 #2
    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: Jul 25, 2004
  4. Jul 25, 2004 #3
    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.
     
  5. Aug 3, 2004 #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
     
  6. Aug 3, 2004 #5

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    Why didn't you just multiply out by hand and subtract?:confused:
     
  7. Aug 3, 2004 #6
    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
     
  8. Aug 4, 2004 #7

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    Oh, I hadn't thought of that! (Or, possibly I had..:wink:)
     
  9. Aug 4, 2004 #8

    Galileo

    User Avatar
    Science Advisor
    Homework Helper

    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: Aug 4, 2004
  10. Aug 4, 2004 #9
    Yes it is, except that it is more formal.

    Thanks and cheers,
    Vivek
     
  11. Aug 4, 2004 #10

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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
     
  12. Aug 4, 2004 #11
    Thanks faust9, Galileo, arildno and NateTG

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


    Cheers
    Vivek
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook