CS 6515 Exam 2 Questions With 100% Correct Answers.

How can you find how many numbers between 1 and x are relatively prime with x. - Answer-For a number to be relatively prime it must share no common factors aside from 1 (gcd(a,b)=1). Thus, first we factor x to find if it has any factors. Then we know if a factor is shared it would have to be these ones, so we can check the factors and multiples of the factors, counting up the number of matches as we go. Then subtract the number of matches from (x-1) and you have the answer. Other numbers can be not prime themselves but relatively prime still to 143. A good check as you iterate up the multiples is that you should reach the number x that you factored eventually. If a modular inverse (a*x ≡ 1 mod(N)) exists, what is the relationship of a and N? - Answer-They are relatively prime to one another; the only common factor is 1. What range do we report the modular inverse in - Answer-1 to N-1 What does Euclid's rule state, and explain why it makes sense - Answer-gcd(x,y) = gcd(x mod y, y) (for x=y) y is going to be one of the target values, so factoring it out of the x term doesn't change the divisor. At a basic level, gcd(x,y) = gcd(x-y,y) and then this scales If d divides x and y, then what can be said about the d dividing x-y - Answer-This works as well and is a way we can verify x and y if the difference is more feasible to calculate on What is the recursion for each step of Euclid's algorithm, and what are the conditions of valid inputs - Answer-E(x,y) = E(y, x mod y) y takes first input to maintain the condition x = y condition x = y = 0 What is GCD(x,0) - Answer-x what is the relation of d, alpha, and beta for GCD(x,y) (where d is the GCD) - Answer-d = x*alpha + y*betaGo from the base case of Euclid to the first step of extended Euclid - Answer-E(1,0) = (1, 0, 1) What is the recurrence for extended euclide - Answer-Given (x', y', d) (y', x' - floor(a/b)*y', d) where a and b are the elements in the Euclid's decomposition at the same level (to the left if you wrote it like in office hours) How do you actually get the mod inv after finishing EE - Answer-It is y' from Ext Euclids, but must make sure to report in range 1 to N