Euclid's Algorithm for Greatest Common Divisor

1. (a) Use the Euclidcan Algorithm to find the greatest common divisor of 13 and 21 (b) Is 13 invertible in Z21? If so, find the reciprocal. (c) Suppose x and yare integers, what is the minimum positive value for 13x+21y? Determine all posible values of (x,y) for which the minimum is obtained. (PLEASE SEE ATTACHMENT FOR ...continues

Lowest Common Multiple Application Word Problem

Five children collect N pieces of Halloween candy and decide to split it evenly among them. When they try to divide it they have two pieces of candy left over. One of the children leaves, taking the 26 pieces of candy she collected with her. The remaining four children try to split the N-26 remaining pieces of candy and discover ...continues

Euler Totient Function (Six Problems)

For this problem it helps to know that: 3x7x13 = 273 (a) Define the Euler Totient function, (SYMBOL) For (b) to (f) please see attached. (PLEASE SEE ATTACHMENT FOR COMPLETE PROBLEM AND PROPER SYMBOLS)

Odd Primes, Inverses and Wilson's Theorem

Assume p is an odd prime ... Please see the attached file for the fully formatted problems.

Proof about congruence modulo 43 (also expressible as equivalence modulo 43)

Let S = Z_43 (where the underscore, "_", indicates that what follows it, in this case 43, is a subscript). Let Q be a subset of S that contains ten non-zero numbers (i.e., that Q contains ten non-zero elements of S). Prove that Q contains four distinct numbers "a," "b," "c," "d" such that ab = cd in Z_43.

Context Free Grammars

Following is a big-oh relationship. Give witnesses n0 and c that can be used to prove the relationship. Choose your witnesses to be minimal, in the sense that n0 - 1 and c are not witnesses, and if d < c, then n0 and d are not witnesses. n¹º is O(3ⁿ)

Context Free Grammars / Languages from Grammars

On the ith round {see attached}, what is the length of the shortest string that is new for either of the syntactic categories? What is the length of the longest new string for: a) b)