I am given the number 7^361 and asked for the last two digits of the number, and to explain why it is correct. I am a little lost on this one.
Can anyone give me some guidance in the right direction.
Thanks in advance!
Are you working in modular arithmetic? My approach would be to raise 7 to different exponents mod 100, and then multiply them together to get 7^361. Take == to be the modular symbol:
7^4 == 1 (mod 100)
7^8 == 1 (mod 100)
7^16 == 1 (mod 100)
..
You'll get to high exponents very quickly. Since 361 = 256 + 64 + 32 + 8 + 1:
(7^256)(7^64)(7^32)(7^8)(7^1) == 1*1*1*1*7 mod(100) == 7 mod(100)
Hope it helps, and apologize if it's wrong.
EDIT: gave you mod 362 instead of 361
Thanks for the replies!
Besides which way is faster, which one is easier to comprehend :P
I am trying to take your solution and break it down so a math feeble individual like myself could apply it to other like problems...:P
Ok so did you pick mod(100) because we want the last 2 digits? mod(10) if we wanted the last 1 and mod(1000) if we wanted the last 3?
Then you took the base 7 and asked "7 to the power of what mod(100) ==1?"
Not sure what you did here though...
EDIT: I am looking at some old assignments and found these questions that are probably a little easier to learn from.361 = 1 (mod 4).
Are there some easy heuristics to calculating these?
These question says compute the following.
5^55 (mod 5).
5^55 (mod 9).
2^21*4^22*6^23 (mod 7)
7777^3333 (mod 10)
if a^k = 1 (mod n)
and b = t (mod k), that is b= t + km,
then a^b = (a^t)(a^km) = (a^t)(a^k)^m = (a^t)(1^m) = a^t (mod n).
the idea is, we don't want to calculate the "big exponent" a^b, but the "small one" a^t, which hopefully is a LOT easier.
so for your other examples:
5 = 0 (mod 5), so 5^(any positive integer) = 0 (mod 5).
the next one: let's first look at powers of 5 mod 9:
5^2 = 25 = 7 (mod 9)
5^3 = (5^2)(5) = 7(5) = 35 = 8 (mod 9)
5^4 = (5^3)(5) = 8(5) = 40 = 4 (mod 9)
5^5 = (5^4)(5) = 4(5) = 20 = 2 (mod 9)
5^6 = (5^5)(5) = 2(5) = 10 = 1 (mod 9) <---bingo, we've found "k", it's 6.
so now we find 55 (mod 6), which is 1.
so 5^55 = (5^6)^9(5) = (1^9)(5) = 5 (mod 9).
(2^21)(4^22)(6^23) (mod 7).
first we need to find some k so that 2^k = 1 (mod 7). prove that 3 is the smallest one that works.
what is 21 (mod 3)? 0. so 2^21 = 2^0 = 1 (mod 7).
how about 4^22 (mod 7)? look at powers of 4 mod 7:
4^2 = 16 = 2 (mod 7)
4^3 = (4^2)4 = 2(4) = 1 (mod 7) <--we want to find 22 (mod 3).
what is 22 (mod 3)? it is 1. so 4^22 = 4 (mod 7).
now for 6^23 (mod 7). powers of 6 mod 7:
6^2 = 36 = 1 (mod 7). so we want to find 23 (mod 2).
23 = 1 (mod 2), so 6^23 = 6 (mod 7).
so (2^21)(4^22)(6^23) = (1)(4)(6) = 24 = 3 (mod 7).
the last one is even easier:
7777 = 7 (mod 10) just look at the last digit.
powers of 7 mod 10:
7^2 = 9 mod 10
7^3 = 3 mod 10
7^4 = 1 mod 10 <---we want to reduce 3333 mod 4.
3333 = 33 (mod 4) (because 100 is divisible by 4)
33 = 1 mod 4.
so 7777^3333 = 7^3333 = 7^1 = 7 (mod 10), which is good because 7777^3333 has more than 12,900 dgits, there's no way we could do this the long way.
Hello, ehpoc!
We have: .$\displaystyle 5^{55}\text{ (mod 5)} \;\;\equiv\;\; 0^{55}\text{ (mod 5)} \;\;\equiv\;\; 0\text{ (mod 5)}$Compute the following:
. . $\displaystyle 5^{55}\text{ (mod 5)}$
$\displaystyle 5^{55}\text{ (mod 9)}$
$\displaystyle \text{We note: }\:\begin{Bmatrix}5^1 & \equiv & 5\text{ (mod 9)} \\ 5^2 & \equiv& 7\text{ (mod 9)} \\ 5^3 &\equiv& 8\text{ (mod 9)} \\ 5^4 & \equiv& 4\text{ (mod 9)} \\ 5^5 & \equiv& 2\text{ (mod 5)} \\ 5^6 &\equiv& 1 \text{ (mod 9)} \end{Bmatrix}\quad\text{Powers-of-5 have a six-step cycle.}$
Hence: .$\displaystyle 5^{55} \;\;=\;\;5^{54}\cdot 5 \;\;=\;\;(5^6)^9\cdot5 \;\;\equiv\;\; 1^9\cdot5 \text{ (mod 9)} \;\;\equiv\;\; 5\text{ (mod 9)}$
$\displaystyle 2^{21}\cdot4^{22}\cdot6^{23}\text{ (mod 7)}$
We have: .$\displaystyle 2^{21}\cdot(2^2)^{22}\cdot(2\cdot3)^{23} \;\;=\;\;2^{21}\cdot2^{44}\cdot2^{23}\cdot3^{23} \;\;=\;\;2^{88}\cdot3^{23}$
$\displaystyle \text{We note: }\;\begin{Bmatrix}2^1 & \equiv& 2\text{ (mod 7)} \\ 2^2 &\equiv& 4\text{ (mod 7)} \\ 2^3 &\equiv& 1\text{ (mod 7)} \end{Bmatrix} \quad\text{Powers-of-2 have a three-step cycle.}$
$\displaystyle \text{Hence: }\:2^{88} \;\;=\;\;2^{87}\cdot 2 \;\;=\;\;(2^3)^{29}\cdot 2 \;\;\equiv\;\;1^{29}\cdot 2\text{ (mod 7)} \;\;\equiv\;\;2\text{ (mod 7)} $
$\displaystyle \text{We note: }\;\begin{Bmatrix}3^1 &\equiv& 3\text{ (mod 7)} \\ 3^2 &\equiv& 2\text{ (mod 7)} \\ 3^3 &\equiv & 6\text{ (mod 7)} \\ 3^4 &\equiv& 4\text{ (mod 7)} \\ 3^5 &\equiv& 5\text{ (mod 7)} \\ 3^6 &\equiv& 1\text{ (mod 7)} \end{Bmatrix} \quad\text{Powers-of-3 have a six-step cycle.}$
$\displaystyle \text{Hence: }\:3^{23} \;\;=\;\;3^{18}\cdot3^5 \;\;=\;\;(3^6)^3\cdot3^5$
. . . . . . . . . $\displaystyle \equiv \; 1^3\cdot5\text{ (mod 7)} \;\;\equiv\;\;1\cdot5\text{ (mod 7)} \;\;\equiv\;\;5\text{ (mod 7)}$
$\displaystyle \text{Therefore: }\:2^{88}\cdot 3^{23}\text{ (mod 7)} \;\;\equiv\;\;2\cdot5\text{ (mod 7)} \;\;\equiv\;\;3\text{ (mod 7)}$
$\displaystyle 7777^{3333}\text{ (mod 10)}$
$\displaystyle \text{Since }\,7777\;\equiv\;7\text{ (mod 10)},\,\text{ we have: }\:7^{3333}$
$\displaystyle \text}We note: }\:\begin{Bmatrix}7^1 &\equiv& 7\text{ (mod 10)} \\ 7^2 &\equiv& 9\text{ (mod 10)} \\ 7^3 &\equiv& 3\text{ (mod 10)} \\ 7^4 &\equiv& 1\text{( mod 10)} \end{Bmatrix} \quad\text{Powers-of-7 have a four-step cycle.}$
$\displaystyle \text{Therefore: }\:7777^{3333} \;\;\equiv\;\;7^{3333}\text{ (mod 10)} \;\;\equiv\;\; 7^{3332}\cdot7\text{ (mod 10)}$
. . . . . . $\displaystyle \equiv\;\;(7^4)^{833}\cdot 7\text{ (mod 10)} \;\;\equiv\;\; 1^{833}\cdot7\text{ (mod 10)} \;\;\equiv\;\; 7 \text{ (mod 10)} $
My brain does not easily think in modular arithmetic (guess because I am just new to it)
SO I am still trying to break this solution down into explicit steps so I could apply it to like problems in the future. Could someone help quick?
So if I have a number A to the power of a 2 digit number I would say "what power of A will give me 1 (mod10)."? And I would say the same thing for A to a three digit power except use mod100? Am i right so far?7^4 = 1 (mod 100).
361 = 1 (mod 4).
so 7^361 = 7^(1+4k) = (7)(7^4)^k (mod 100)
= (7)(1)^k (mod 100)
= 7 (mod 100). so the last 2 digits are "07".
What is happening after that in this solution??
if you are looking for "the last digit" that is the same thing as reducing mod 10. if you are looking for "the last two digits" that is the same as reducing mod 100.
in general, if you are trying to solve a^b mod n, where a and b are really, really big, you want to find an equivalent problem where a and b are smaller.
now, for some "n"s you can't always find some power of a that equals 1 mod n (but you can if a and n are co-prime).
but...if you CAN, then you can calculate "the cycles within the cycle" that we get for n.
so we start with:
a^b = ? (mod n) and maybe both a and b are BIG. to make a smaller, replace it with a' which is less than n, by reducing mod n.
so now we have:
a'^b = ? (mod n) <---same problem, but now a' is a smaller number (less than n).
(if a is already less than n, we can skip this step).
next, we look at powers of a mod n:
a, a^2, a^3,....<--look for something that is 1 mod n.
let's say the k-th power of a is 1 mod n. then this is GOOD, we can use this fact to make our problem easier.
if (a^k) = 1, the next step is to calculate b (mod k) (remember, b was our original exponent, if we make it smaller, this is good).
why does this work? suppose b (mod k ) is (shoot, we need another letter) c.
what does this mean? it means b = k(something) + c (and ANOTHER letter...i hope i don't run out):
b = kt + c (we don't really care what t is, we're not going to use it).
a^b = a^(kt+c) = (a^(kt))(a^c) <---by the rule of exponents, nothing modular here, yet
= (a^k)^t(a^c) <---another rule of exponents: a^(kt) = (a^k)^t.
NOW....what happens when we take everything "mod n"?
well, a^k (mod n) is 1, so (a^k)^t (mod n) is (1)(1)....(1) (t times) (mod n)
which is 1 (mod n). so that entire (a^(kt)) factor, just "drops out", leaving us with c, which is smaller than b.
so now we have a'^c ,and we've trimmed a lot of size off of a AND b, hopefully enough to make the calculation EASY.
here's what happens "under the hood": when we take a number "mod n", we're taking the number LINE, and wrapping it around a circle (just like a clock). we don't care about how many times we go around, all we care about is how far past a multiple of n we are, when we stop. so modular numbers "act different" than what we are used to. for example, 5 doesn't look very much like 1, but it is (mod 4). since 1*1*1 = 1, we might hope that 5*5*5 is 1 mod 4. let's prove this two ways:
5*5*5 = 125 = 124 + 1 = 4(31) + 1 <---125 is 1 more than a multiple of 4.
5*5*5 = (1+4)(1+4)(1+4) = 1(1+4)(1+4) + 4(1+4)(1+4) <---the 2nd term is a multiple of 4, we can just leave it like that.
= (1+4)(1+4) + 4(1+4)(1+4) = (1+4) + 4(1+4) + 4(1+4)(1+4)
= (1+4) + 4[(1+4) + (1+4)(1+4)] <---ok, it's messy, but it's just one big "multiple of 4"
= 1 + 4[1 + (1+4) + (1+4)(1+4)] <--- and the messy part goes away now, because we don't care about how many multiples of 4 we have, just the remainder
= 1 (mod 4)
the point is, using modular numbers, takes problems involving BIG numbers, and turns them into problems involving smaller numbers.
well you're not going to find one, because 6 and 100 aren't co-prime (they share a common factor of 2).
but let's look at powers of 6 mod 100 anyway:
6^1 = 6
6^2 = 36
6^3 = 16
6^4 = 96
6^5 = 76
6^6 = 56
6^7 = 36 <---we're starting to repeat, with a cycle length of 5.
6^8 = 16
so let's figure out what 337 is mod 5, which is easy it's 2.
so 6^337 = (6^(5k))(6^2) = 6^2 (mod 100)
= 36 (mod 100).
I am looking over this thread again because there is a strong possibility this is going to be on the final.
I think I completely understand Deveno's explantion on how to solve it (how could I not it was awesomely detailed!)
Now I just have a funny question. Could someone provide me with a similar question to finding 7^361(mod100) that will solve using the same technique. I know it sounds funny but I can't come up with a good one myself. I just want to practice what I have learned. Thanks!