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. 👍
2. 👎
3. 👁

Similar Questions

1. maths

when a 3 digits number is reversed, the number decreases by 396. the diffrence between the digits at the units place and the digit at the tens place is the same as the difference between the digits at the tens place and the

2. math

The digits 2, 4, 6, 8 and 0 are used to make five-digit numbers with no digits repeated. What is the probability that a number chosen at random from these numbers has the property that the digits in the thousands place and ten's

3. math

A positive two-digits number is such that the product of the digits is 24.When the digits are reversed,the number formed is greater than the original number by 18.Find the number

4. math

Solve the mathematical puzzle. Determine the digits of Q from these clues. The first and third digits of Q are even. The second and fourth digits of Q are odd. The first digit is two times the fourth digit. The first and second

1. Math

A number of two digits is such that twice the ten digits is 8 less than seven times the unit digit. When the digits are reversed, the number is decreased by 9. What is the number?

2. math30

A security code used to consist of two odd digits, followed by four even digits. To allow more codes to be generated, a new system uses two even digits, followed by any three digits. If repeated digits are allowed, the increase in

3. math: probability

A locker combination has three nonzero digits, and digits cannot be repeated. If the first two digits are even, what is the probability that the third digit is even?

4. Pre

How many different license plate number can be made using 2 letters followed by 4 digits selected from the digits 0-9 a) if letters and digits may be repeated? b) if letters may be repeated, but digits may not be repeated? c) if

1. Math

I am a 4-digit even number. I am less than 2500. The digits in my hundreds and the tens place is different. The digits in my hundreds place are less than the digits in the one thousands place. The sum of my last 2-digits equal 9.

2. Mathematics

A number of two digits is increased by 9. When the digits are reversed, the sum of the digits is 5. Find the number.

3. Math

1. Is 26 divisible by 2? A. No. B. Yes, because 2 + 6 = 8 and 8 is divisible by 2. C. Yes, because the last digit is 6, which is divisible by 2. 2. Is 216 divisible by 3? A. No. B. Yes, because the sum of 2 + 1 + 6 = 9, which is

4. 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