Thread: Can someone help me understand these problems please? Should be fairly simple...

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

Originally Posted by matthayzon89

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

]

For (a) use that , whenever m,n are coprime.

As for (b)-(c) check carefully the questions and check carefully what you write. As they appear in your OP they make no sense.

Tonio

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

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

From Wikipedia: "If p is prime, then for integer , . Moreover, is a multiplicative function; if m and n are coprime then ." Therefore, .

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

It's easy to understand why . Indeed, , and .

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.

C)Find the value of x such that: 9 * x 1 mod 10

One option is to search through all possible x from 0 to 9. It is easy to see that .

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 .

I still dont understand why -55 mod 7 = 1 where does 7*8 come in? it is not given....

Also,
52^6 mod 73 = 27 How would you determine this WITHOUT using a calculator? My calculator results in an incorrect answer due to rounding

52^6 mod 73 = 27 How would you determine this WITHOUT using a calculator? My calculator results in an incorrect answer due to rounding

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

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.

I still dont understand why -55 mod 7 = 1 where does 7*8 come in? it is not given....

We have for any k. In other words, you can add or subtract m without changing the number modulo m.

Originally Posted by matthayzon89

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

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

C)Find the value of x such that: 9 * x 1 mod 10 <- I have no clue

You are missing an "=" aren't you? Do you mean "solve 9x= 1 (mod 10)"?

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