1. Show that 11,111,111 and 3,333,333 are relatively prime using the Extended Euclidean Algorithm.

2. Use the EEA to find the GCD of 6,327 and 10,101.

3. Find the additive inverse of 3,333,333 modulo 11,111,111. Verify.

4. Find the multiplicative inverse of 3,333,333 modulo 11,111,111.Verify.

5. What is the orbit of 3 in the group Z_7 under multiplication modulo 7? Is 3 a generator?

Solutions

Expert Solution

Colby Messinger answered 2 years ago

Next > < Previous

Related Solutions

a. Using the Euclidean Algorithm and Extended Euclidean Algorithm, show that gcd(99; 5) = 1 and...

a. Using the Euclidean Algorithm and Extended Euclidean Algorithm, show that gcd(99; 5) = 1 and find integers s1 and t1 such that 5s1 + 99t1 = 1. [Hint: You should find that 5(20) + 99(?1) = 1] b. Solve the congruence 5x 17 (mod 99) c. Using the Chinese Remainder Theorem, solve the congruence x 3 (mod 5) x 42 (mod 99) d. Using the Chinese Remainder Theorem, solve the congruence x 3 (mod 5) x 6 (mod 9)...

Write a program( preferably in C++) using the extended Euclidean algorithm to find the multiplicative inverse of...

Write a program( preferably in C++) using the extended Euclidean algorithm to find the multiplicative inverse of a mod n. Your program should allow user to enter a and n. Note: For this question please make sure the code compiles and runs, it is not copied and pasted from elsewhere( I will be checking!). Thanks

find a linear combination for gcd(259,313). use extended euclidean algorithm. what is inverse of 259 in...

find a linear combination for gcd(259,313). use extended euclidean algorithm. what is inverse of 259 in z subscript 313? what is inverse of 313 in z subscript 259?

Using extended euclidean algorithm find f(x) and g(x) in: f(x)(x^5 + 4x^4 + 6x^3 + x^2...

Using extended euclidean algorithm find f(x) and g(x) in: f(x)(x^5 + 4x^4 + 6x^3 + x^2 + 4x + 6) + g(x)(x^5 + 5x^4 + 10x^3 + x^2 + 5x + 10) = x^3+1

Suppose you Do not know anything about Extended Euclidean Algorithm. How to find t(x) and s(x)...

Suppose you Do not know anything about Extended Euclidean Algorithm. How to find t(x) and s(x) that satisfy the greatese common divisor of f(x) and g(x) equals to f(x)t(x)+g(x)s(x) in Q(x). You can give me an example(polynomials) if you want. Thank you!

Using Euclidean algorithm, Find integers x and y with 65537x + 3511y = 17.

All necessary steps much show for these problems, please. Use the Euclidean algorithm to find gcd(12345,...

All necessary steps much show for these problems, please. Use the Euclidean algorithm to find gcd(12345, 54321). Write gcd(2420, 70) as a linear combination of 2420 and 70. The work to obtain the gcd is provided. 2420 = 34(70) + 40 70 = 1(40) + 30 40 = 1(30) + 10 30 = 3(10) + 0 Determine if 1177 is prime or not. If it is not, then write 1177 as a product of primes Find gcd(8370, 465) by unique...

use euclidean algorithm to find integers m,n such that 1693m+2019n=1

Q3 (a) Briefly describe the extended Euclidean plane, and explain how it satisfies the axioms of...

Q3 (a) Briefly describe the extended Euclidean plane, and explain how it satisfies the axioms of projective geometry. (b) Describe the Real Projective Plane RP2, explaining what points and lines in RP2 correspond to in R 3 with respect to an ‘all-seeing eye’ at the origin. (c) Prove that the Cross-Ratio is preserved by every projective transformation

Prove Desargues’ Theorem for the case where AC is parallel with A′C′ on the extended Euclidean...

Prove Desargues’ Theorem for the case where AC is parallel with A′C′ on the extended Euclidean plane.

Subjects