Note that this argument also shows that processors needn't keep track of which processors they have received messages from -- that is, that it's enough for processors to simply count the number of incoming messages.

1. One way of finding a generator is by trial and error. If the first residue tested is 2, then success is immediate, since the powers of 2 mod 29 from the 1st to the 28th are
   2, 4, 8, 16, 3, 6, 12, 24, 19, 9, 18, 7, 14, 28, 27, 25, 21, 13, 26, 23, 17, 5, 10, 20, 11, 22, 15, and 1.

2. For any generator g modulo a prime p, and divisor k of p-1, the kth roots are just the values of g^i(p-1)/k, as i ranges from 0 to k-1. So since 2 is a generator, the square roots of 1 are {2⁰, 2¹⁴} = {1, 28}, and since 1 is also a 1st root of 1, the only primitive square root of 1 is 28 (also known as -1).

   The 4th roots of 1 are {2⁰, 2⁷, 2¹⁴, 2²¹} = {1, 12, 28, 17}. Of these, 1 and 28 will give 1 when raised to lower powers than 4, so 12 and 17 are primitive.

   The 7th roots of 1 are {2⁰, 2⁴, 2⁸, 2¹², 2¹⁶, 2²⁰, 2²⁴} = {1, 16, 24, 7, 25, 23, 20}. Of these, only 1 will give 1 when raised to a lower power than 7, so 16, 24, 7, 25, 23, and 20 are primitive.

   The 14th roots of 1 are {2⁰, 2², 2⁴, 2⁶, 2⁸, 2¹⁰, 2¹², 2¹⁴, 2¹⁶, 2¹⁸, 2²⁰, 2²², 2²⁴, 2²⁶} = {1, 4, 16, 6, 24, 9, 7, 28, 25, 13, 23, 5, 20, 22}. Of these, 1 and 28 and 16, 24, 7, 25, 23, and 20 will give 1 when raised to a lower power than 7, so 4, 6, 9, 13, 5, and 22 are primitive.

   Modulo 29, there must be φ(28) = 28(1/2)(6/7) = 12 generators. The generators may be found by selecting those exponents which are relatively prime to 28, or by starting with the entire set of units and removing the elements we have found to have an order less than 28. In any case, the 12 residues obtained are 2, 8, 3, 19, 18, 14, 27, 21, 26, 10, 11, and 15, and these are the generators.

3. EXTRA CREDIT: Using the notation above, the primitive kth roots of 1 may be found by choosing those values of i that are relatively prime to k.

   In the example above, the primitive 2nd root has i = 1, giving an exponent of 14. The primitive 4th roots have i relatively prime to 4, so i is 1 or 3, and the exponents are 7 and 21. The primitive 7th roots have i relatively prime to 7, so i may be 1, 2, 3, 4, 5, or 6, and the exponents are 4, 8, 12, 16, 20, and 24. The primitive 14th roots have i relatively prime to 14, so i may be 1, 3, 5, 9, 11, or 13, and the exponents are 2, 6, 10, 18, 22, or 23. The primitive 28th roots have i relatively prime to 28, so i (and therefore the exponent) may be 1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25 or 27. Note that every exponent appears exactly once (except for 0, which is the exponent of the primitive 1st root of 1).

1. The recursive arguments for the Euclidean GCD algorithm are given at left below, and are computed top down. The coefficients in parentheses at right below are computed bottom up.

     GCD(216, 7)         1 = 216(-1) +  7(1-[-1]30) = 216(-1) + 7(31)
     GCD(  7, 6)         1 =   7(1)  +  6(0-[1]1) = 7(1) + 6(-1)
     GCD(  6, 1)         1 =   6(0)  +  1(1)
     GCD(  1, 0)         1 =   1(1)  +  0(0)
   

   So the reciprocal of 7 mod 216 is 31.

2. Mod 247, we have

   1281 = 128
   1282 = 82
   1283 = 122
   1286 = 64
   1287 = 41
   12814 = 199
   12815 = 31
   12830 = 220
   12831 = 2
   

The computation will differ for the other test, depending on the value of x. But for example, if x = 0101010011₂ = 339, then 3x = 1017, and the exponentiation algorithm would start with the witness 2 and compute the powers of 2 with exponents 2, 3, 6, 7, 14, 15, 30, 31, 62, 63, 126, 127, 254, 508, and 1016. The respective powers are 4, 8, 64, 128, 112, 224, 343, 686, 742, 467, 451, 902, 4, 16, and 256. Since this last power is not 1, we may safely conclude that 1017 is composite. For other values of 3x, additional witnesses may be required.