last digit of large number

[galactus]

Something I am learning more about is modular arithmetic. Admittedly, I do not know that much but what to learn more. The 'basics' anyway, for lack of a better term.

How does one use mod arithmetic to find the last 2 digits of a huge number.

For instance, suppose I wanted to know the last digit of \(\displaystyle \L\\1923^{1929}\)

How is that done?. I tried to find some resources but was unable to find anything about this particular topic.

I did find one link on mathforum:

The last digit of \(\displaystyle 1996^{1996}\)

It said, "They then rewrote the equation as \(\displaystyle (-4)^{1996} (mod 100)\), factored out
the exponent, and solved the equation by getting rid of all the
numbers except the tens and ones digit after every step. They ended
up with an answer of 96".

 

[stapel]

I would just look for a pattern in the ones digit; namely, the 3.

. . . . .3⁰ = 1
. . . . .3¹ = 3
. . . . .3² = 9
. . . . .3³ = 27
. . . . .3⁴ = 81
. . . . .3⁵ = 243

...and so forth. The ones digits cycle as 1, 3, 9, 7, 1, 3, 9, 7, ....

Since, at every stage, you'll be multiplying the last ones digit by 3, the ones digits must necessarily follow this pattern.

Where does "1929" fall in this pattern?

Eliz.

 

[galactus]

Thanks, Stapel, for the response. I should've said 'last 2 digits'. I was more interested in the modular thing.

 

[daon]

Well, using the same idea, 1923 = 23 (mod 100). All calculations here are done mod 100 if not otherwise mentioned. There are also probably better ways of approaching this type of problem.

Thus the last two digits of your exponential will be the same last two digits in 23¹⁹²⁹. This is true since [1923] = [1900 + 23] = [1900] + [23] = [100*19] + [23] =[0]+[23] = [23]. Where [x] is the representative of all integers that equal x mod 100, i.e. [52] = [252] = [-48], etc...

Then you can ask yourself simple questions like: What is 23¹⁰ (mod 100)? A simple calculation shows that it is 49. Similarly, 23⁹ (mod 100) is 63.

23¹⁹²⁹ = (23¹⁰)¹⁹⁰*(23¹⁰)²*23⁹ = (49¹⁰)¹⁹(49)²*63

Continuing we see that 49¹⁰=1 and 49²=1. So we have 1*1*63=63. Whew...

In case you didn't notice, this way is a bit sloppy and with just two "simple" theorems from Euler and Lagrange it is quite simplified. I'm not sure if these tools are available to you, so I won't go into detail.

By Euler's Phi function we have that there are 40 integers less than or equal to 100 that only have 1 as a common divisor with 100 (integers relatively prime to 100). As an application of Lagrange's theorem for finite groups, any number in this group of integers raised to the power of 40 (the amount of positive #s relatively prime to 100) equals one.

Notice that 23 is in this group. Therefore 23^40k=1 (mod 100).
We have 23¹⁹²⁹ = 23^(48)(40)23⁹ = 1*23⁹ = 63. This is also true for -77 since 23=-77 (mod 100).

Of course if you had noticed that 23²⁰=1, it would have been easier, too. I hope that has been of help.

-Daon

 

[galactus]

Thanks, Daon. It was helpful. I am not totally clueless regarding mod arithmetic. Just want to learn more. Your input was indeed helpful. Thanks.

I am familiar with Euler's phi function.