Find the last digit of the sum of two numbers with large exponents.

[johnnyICON]

Hi, I am trying to solve this question in my textbook. It asks me to find the last digit of the following expression:

222^{555} + 555^{222}

Now, I have tried using modular arithmetic to solve this question, but I'm stuck.
And I'm not all too sure if took the right approach or not, any hints?

 

[shmoe]

You should be able to do the two terms separately, can you find 555^222 mod 100? 222^555 mod 100?

It might make the arithmetic a little easier if you consider powers of 2, 5, and 11 mod 100 separately but this isn't mandatory.

 

[johnnyICON]

I did something like that. I used mod 11 for both numbers. Found 222 congruent to 2 mod 11, and 555 congruent to 5 mod 11.

So I made the statement that 222^{555} \equiv 2^{555} mod 11and 555^{222} \equiv 5^{222} mod 11

Then, I did successive powers of both 2 and 5 and found their congruencies until I found a pattern.

I determined that after five successive powers of 5, the congruencies would repeat. And after ten successive powers of 2, the congruencies would repeat.

So I divided the the exponents 222 and 555 by 10 and 5, respectively, to find another congruency. And that's where I get stuck.

 

[shmoe]

Sorry, I was misleading in my last post. For some reason I thought you wanted the last two digits, not just the last one. To find the last digit you need only find 222^555 and 555^222 mod 10, which will be easier than finding them mod 100. This also means the bit about 11 is superfluous.

 

[johnnyICON]

Maybe you can take a look at this example:

Example. Find the last digit of 7^{100}.
We need to evaluate 7^{100} (mod 10). Since 7^2 = 49\equiv −1 (mod 10) we have 7^{100} \equiv (72)^{50} \equiv (−1)^{50} \equiv 1 (mod 10).Thus the last digit is 1.

Is the last digit 1 because of the last congruency?

 

[johnnyICON]

I am trying to apply this process that I found online to solve my problem.

I get stuck at the point where I divide the exponent by the length of the pattern.

http://mathcentral.uregina.ca/QQ/database/QQ.09.04/landon1.html

 

[shmoe]

Yes, the last digit of 7^100 is 1 because they've shown that the remainder you get when you divide 7^100 by 10 is 1.


So you look at the powers of 2 and find the pattern is 4 digits long. So 2^1, 2^5, 2^9, 2^13, ...2^105, ... are all congruent to 2 mod 10. Essentially you can add a 4 to the exponent and not affect the result. Same with 2^2, 2^6,... In the language of congruences, if a\equiv b\ mod\ 4 then 2^a\equiv 2^b\ mod\ 10. There is a good reason why this is true, a power of 2's congruence class mod 10 is completely determined by its congruence class mod 5 (Chinese remainder theorem if you've met it) and we know 2^4\equiv 1\ mod\ 5.

In the link you provided, they have a\equiv b\ mod\ 4 implies 7^a\equiv 7^b\ mod\ 10 (we actually know here 7^4\equiv 1\ mod\ 10). So to find 7^{358}\ mod\ 10 notice 358\equiv 2\ mod\ 4 so 7^{358}\equiv 7^2\equiv 9\ mod\ 10.

 

[johnnyICON]

Wow, that makes a lot of sense now. And thanks for relating to the link I provided. I was really uncertain about this part::

notice 358\equiv 2\ mod\ 4 so 7^{358}\equiv 7^2

When I divided the exponent by the length and found its congruence, I wasn't sure if it meant that 7^{358}\equiv 7^2 or if it meant 7^{358}\equiv 7^{2 (mod 4)}.

So when dealing with congruencies, I can replace a with b by symmetry right? That is, 358\equiv 2\ mod\ 4 is equivalent to 2\equiv 358\ mod\ 4.

 

[shmoe]

When I divided the exponent by the length and found its congruence, I wasn't sure if it meant that 7^{358}\equiv 7^2 or if it meant 7^{358}\equiv 7^{2 (mod 4)}.

7^{358}\equiv 7^2\ mod\ 10 would be the correct one. You don't usually put "mod" up in an exponent.

So when dealing with congruencies, I can replace a with b by symmetry right? That is, 358\equiv 2\ mod\ 4 is equivalent to 2\equiv 358\ mod\ 4.

Yep. The "modular equivalence" works in many ways like your usual equal sign. It's symmetric, transitive and reflexive.

 

[johnnyICON]

Great! Thanks a lot shmoe, you've helped a lot! Too bad I couldn't rate your help.
10/10