Hello All,
I am currently preparing for an upcoming test. I know most of the material but the problems below is what I got stuck on, any help will be greatly appreciated!
A) Determine φ(77) *Euler Totient function for 77+. (The first step is finding the largest number that you can multiply to get 77, i believe which is 7 and 11).
B) -55 Mod 7= 1 (<- I dont understand. I know that -7 mod 55 equals 48 but I can't understand how they got 1 from -55 mod 7).
C)Find the value of x such that: 9 * x 1 mod 10 <- I have no clue
Okay, thanks for your help...
Can anyone help me figure out a way to compute 52^6 mod 73 = 27
When I use a TI-83 to compute it, it gives me the answer in scientific notation and my answer ends up being incorrect due to rounding.
Is there an easier way to make this number smaller somehow to get the correct remainder?
Thanks...
From Wikipedia: "If p is prime, then for integer , . Moreover, is a multiplicative function; if m and n are coprime then ." Therefore, .A) Determine φ(77) *Euler Totient function for 77+. (The first step is finding the largest number that you can multiply to get 77, i believe which is 7 and 11).
It's easy to understand why . Indeed, , and .B) -55 Mod 7= 1 (<- I dont understand. I know that -7 mod 55 equals 48 but I can't understand how they got 1 from -55 mod 7).
I am not sure how you defined -55 Mod 7. It may be defined as a function returning the remainder when -55 is divided by 7. Then the exact result depends heavily on the definition. I know that there are all kinds of similar functions in programming languages: some return only positive numbers, others return the same sign as the first argument (-6 in this case), etc.
One option is to search through all possible x from 0 to 9. It is easy to see that .C)Find the value of x such that: 9 * x 1 mod 10
Another way relies on the Euclidean algorithm and its consequence, Bézout's identity. The latter says that, since gcd(9,10) = 1, there exist integers s and t such that 9s+10t = 1. In general, s and t can be found working backwards the computation of the Euclidean algorithm; here it is obvious that -1 * 9 + 1 * 10 = 1. Considering this equality modulo 10, we get . Now, , so .
Get a more powerful calculator , like this one (it's a shame I could not find a better-looking one). Or use an interpreter for a programming language that handles arbitrary-precision arithmetic, such as Scheme. Here you can evaluate expression like (modulo (expt 52 6) 73) or (expt 2 1000).52^6 mod 73 = 27 How would you determine this WITHOUT using a calculator? My calculator results in an incorrect answer due to rounding
Seriously, note that in calculating the remainder of 52 * 52 * 52 * 52 * 52 * 52 and 73 you can perform multiplication and finding remainder in an arbitrary order. You could do all multiplications first and divide then, or could take remainders first, multiply, and find the remainder last (this would be no different in this case because 52 mod 73 = 52.) However, note also that 52 * 52 mod 73 = 3.
We have for any k. In other words, you can add or subtract m without changing the number modulo m.I still dont understand why -55 mod 7 = 1 where does 7*8 come in? it is not given....
7 divides into 55 7 times with remainder 6: 55= 7(7)+ 6. Of course, 6= -1 (mod 7) (since 6= 7- 1) so 55 = -1 (mod 7). Now multiply the equation by -1.
Another way to say that: -55= -8(7)+ 1
You are missing an "=" aren't you? Do you mean "solve 9x= 1 (mod 10)"?C)Find the value of x such that: 9 * x 1 mod 10 <- I have no clue
That means you are seeking a multiple of 9 that is 1 more than a multiple of 10. 9*9= 81.
More formally, you are looking for x such that 9x- 10k= 1 for some number k.
9 divides into 10 once with remainder 1: 1(10)- 1(9)= 1 (I bet you already knew that!!) which means that we can set x= -1, k= -1. x= -1= 9 (mod 10).