# Geometry and Discrete Mathematics (Proofs)

Observe that the last two digits of 7^2 are 49, the last two digits of 7^3 are 43, the last two digits of 7^4 are 01, and the last two digits of 7^5 are 07. Prove that the last two digits of 7^201 are 07.

7^2 = ...49
7^3 = ...43
7^4 = ...01
7^5 = ...07

7^201 = ...07

Break 201 into a product of primes. Hint: 201 is divisible by 3.

Yes, but what would I do with 67 and 3?

You should use modular arithmetic. This works as follows. On the set of integers you define a so-called equivalence relation E which in this case is:

n1 E n2 if n1 - n2 = 100*k

where k is an integer. So, two integers are equivalent if they differ by a miltiple of 100.

We then use the notation [n] for the set of all integers that are related to n via the equivalence relation.

So, e.g.  = {....,-97,3,103,...}

There are then 100 such sets:

, , , ..., .

Note that  and  are the same sets.

On the set M = {,,...} (the so-called quotient set) you can define addition and multiplication:

[n1] + [n2] = [n1 + n2]

[n1]*[n2] = [n1*n2]

Modular artithmetic is just doing calculations on the set M. You can write that  =  instead of saying that 102 is related to 2. Another notation is:

102 = 2 Mod(100)

Anyway, modular artithmetic (modulo 100 in tis case) allows you to calculate what you want. If we delete the square brackets (or the Mod symbol):

7^4 = 1

Raise both sides to the 50-th power

7^200 = 1

and then multiply by 7:

7^201 = 7

In the general case where you have to compute:

X^Y Mod N

and there are no obvious shortcuts, it is simplest to write down the binary representaton of Y:

Y = a_{r} 2^r + a_{r-1}2^(r-1) + ..

where the a_{r} are either 1 or zero.

This means that:

Y = 2^(r1) + 2^(r2) + ...

for some r1 > r2 > ...

You can then write:

X^Y = X^[2^(r1)]*X^[2^(r2)]

So, all you have to do is to raise X to the appropriate powers of two and then multiply these things together. Raising X to such powers can be done by repeatedly squaring X.

E.g. what is

2^(1133) Mod 41?

Expand 1133 in binary system. You can do that easily by subtracting 1 if you can't divide by 2 and then dividing by 2 repeatedly until the number becomes odd, subtracting 1 again and repeating the process:

1133 = 1 + 1132

1132 = 4*283

283 = 1 + 2*141

141 = 1 + 4*35

35 = 1 + 2*17

17 = 1 + 16

1133 = 1 + 4*(1 + 2*(1+4*(1+2*(1+16))))=

1 + 4 + 8 + 32 + 64 + 1024

Note that the powers of two you get in here are just the "cumulative" product of the factors of two you get when you work your way through reducing 1133 by repeatedly subtracting 1 and dividing by two.

You then calculate the powers:

2^1 = 2

2^4 = 16

2^8 = 16^2 = 10

2^16 = 10^2= 100 = 18

2^32 = 18^2 = 37

2^64 = 37^2 = (-4)^2 = 16

2^128 = 16^2 = 2^8 (already alculated)

2^(1024) = 2^64 = 16

So we obtain:

2^1133 = 2*16*10*37*16*16 = 33

1. 👍 0
2. 👎 0
3. 👁 144

## Similar Questions

1. ### math

1. a door code is made up of six unique digits the last digit is 8. 2.oddd and even digits alternate(o is even) 3.the difference of the adjacent is always bigger than 1. 4.the first 2 digits (reads as one number)as well as he two

asked by tony on July 16, 2008
2. ### math

Solve the mathematical puzzle. Determine the digits of F from these clues. The digits of F are all the same. The sum of all the digits of F is 12. The answer when any two of the digits are multiplied together is also 9. F is a

asked by Bria S. on June 30, 2013
3. ### math

x has 3 digits. the tens digits is half the hundreds digits. the number is odd.the sum of the digits is 9

asked by hamza on November 23, 2009
4. ### math

using digits 1-9 only once, multiply a 3 digit by a 2 digit number and get a 4 digit result 12*345=4140? looks ok to me. the answer would have to be 6789 or some order of those digits if you used the others in the question. digits

asked by Trey on November 28, 2006
5. ### Pre Calculus 30

1.How many positive three-digit integers can be made from the digits {3,4,5,6,7} if digits may be repeated? 5x4x3=60 2.In how many ways can all of the letters of the word HEXAGON be arranged if the arrangement must start with a

asked by John on February 20, 2017
6. ### Math

What do the digits in the number 15 add up to? Answer 1+5=___. Using single digits, how many different ways can you add up to 6?. Example: The least number of digits is 2, and it is 1+5=6. The greatest number of digits is 6, and

asked by Mohammed on March 21, 2010

When a computerized generator is used to generate random digits, the proability that any particular digit in the set {0,1,2, . . .,9} is generated on any individual trial is 1/10-0.1. suppose that we are generating digits one at a

asked by david on January 24, 2007
8. ### math

A two digit numbers is three times the sum of the digits. It is 45 less than the number formed when the digits are interchanged. Find the two digits Please anyone to help me with solution

asked by kevi on June 6, 2019
9. ### statistics

For 100 consecutive day frequencies of occurrence of the digits 35,35,30 for the digits 1,2,3 at .05, can you reject the hypothesis that the digits are from a uniform population?

asked by Michael on May 2, 2012
10. ### MATH

A number has three distinct digits. The sum of the digits equals the product of the digits. How many three-digit numbers satisfy this condition?

asked by Jhon on September 3, 2016
11. ### statistics

For 100 consecutive day frequencies of occurrence of the digits 35,35,30 for the digits 1,2,3 at .05, can you reject the hypothesis that the digits are from a uniform population?

asked by Michael on May 2, 2012

More Similar Questions