Discrete Mathematics—Problem Set 2

Problem set instructions:

1.  (Power set)

In problem 1, arithmetic operations are mod n.

(a.)

Let ® denote the mapping of a function from one value to another.  We will show that a ® a^k is never one-to-one.  a is an element of Z_n.  Z_n has values that range from 0 to (n – 1).  k can be any positive integer, but a^k still has to fall within Z_n since we are working with multiplication (mod n).  Therefore, if we compute a^k for more than n values, it must repeat since there are only n elements in Z_n.  This means k ® a^k and l ® a^l.  Since a^k = a^l, we re-write these functions to be k ® a^k and l ® a^l.  Therefore the function is not one-to-one since two x values go to the same y value.

(b.)

We will show the implication: If a is invertible, then there is a positive integer k with a^k = 1.  From part a, we know there is always an l such that a^k = a^l, and k ¹ l.  Since the two constants, k and l, are not equal, one is greater.  We know that b is invertible if a * b = 1.

Start with              a^k = a^l.

Multiply by b^k, arbitrarily choosing l to be the larger integer.

                        b^k * a^k = a^l * b^k

Simplify.               1 = a^{l – k}

Thus, we have proven 1 = a^k when the exponent is l – k.

(c.)

0 has no power or order in any Z_n since it is not invertible.  We can check for the invertability of a by looking for a and b such that a * b = 1 mod n.

       Z₅ = {0,1,2,3,4}

       1:     1¹(mod 5) = 1.              The order of 1 is 1.

2:     2¹(mod 5) = 2.             The order of 2 is 4.

              2²(mod 5) = 4

              2³(mod 5) = 3

              2⁴(mod 5) = 1

3:     3¹(mod 5) = 3.              The order of 3 is 4.

       3²(mod 5) = 4

       3³(mod 5) = 3

       3⁴(mod 5) = 1

4:   4¹(mod 5) = 4.                The order of 4 is 2.

       4²(mod 5) = 1

Z₉ = {0,1,2,3,4,5,6,7,8}

1:     1¹(mod 9) = 1.              The order of 1 is 1.

2:     2¹(mod 9) = 2.              The order of 2 is 6.

       2²(mod 9) = 4

       2³(mod 9) = 8

       2⁴(mod 9) = 7

       2⁵(mod 9) = 5

       2⁶(mod 9) = 1

3:     3 is not invertible with Z₉.

4:     4¹(mod 9) = 4.              The order of 4 is 3.

       4²(mod 9) = 7

       4³(mod 9) = 1

5:     5¹(mod 9) = 5.              The order of 5 is 6.

       5²(mod 9) = 7

       5³(mod 9) = 8

       5⁴(mod 9) = 4

       5⁵(mod 9) = 2

       5⁶(mod 9) = 1

6:     6 is not invertible with Z₉.

7:     7¹(mod 9) = 7.              The order of 7 is 3.

       7²(mod 9) = 4

       7³(mod 9) = 1

8:     8¹(mod 9) = 8.              The order of 8 is 2.

       8²(mod 9) = 1

Z₁₁ = {0,1,2,3,4,5,6,7,8,9,10}.  All elements in Z₁₁ are invertible. 

1:     1¹(mod 11) = 1.             The order of 1 is 1.

2:     2¹(mod 11) = 2.             The order of 2 is 10.

       2²(mod 11) = 4

       2³(mod 11) = 8

       2⁴(mod 11) = 5

       2⁵(mod 11) = 10

       2⁶(mod 11) = 9

       2⁷(mod 11) = 7

       2⁸(mod 11) = 3

       2⁹(mod 11) = 6

       2¹⁰(mod 11) = 1

3:     3¹(mod 11) = 3.             The order of 3 is 5.

       3²(mod 11) = 9

       3³(mod 11) = 5

       3⁴(mod 11) = 4      

       3⁵(mod 11) = 1

4:     4¹(mod 11) = 4.             The order of 4 is 5.

       4²(mod 11) = 5

       4³(mod 11) = 9

       4⁴(mod 11) = 3

       4⁵(mod 11) = 1

5:     5¹(mod 11) = 5.             The order of 5 is 5.

       5²(mod 11) = 3

       5³(mod 11) = 4

       5⁴(mod 11) = 9

       5⁵(mod 11) = 1

6:     6¹(mod 11) = 6.             The order of 6 is 10.

       6²(mod 11) = 3

       6³(mod 11) = 7

       6⁴(mod 11) = 9

       6⁵(mod 11) = 10

       6⁶(mod 11) = 5

       6⁷(mod 11) = 8

       6⁸(mod 11) = 4

       6⁹(mod 11) = 2

       6¹⁰(mod 11) = 1

7:     7¹(mod 11) = 7.             The order of 7 is 10.

       7²(mod 11) = 5

       7³(mod 11) = 2

       7⁴(mod 11) = 3

       7⁵(mod 11) = 10

       7⁶(mod 11) = 4

       7⁷(mod 11) = 6

       7⁸(mod 11) = 9

       7⁹(mod 11) = 8

       7¹⁰(mod 11) = 1

8:     8¹(mod 11) = 8.             The order of 8 is 10.

8²(mod 11) = 9

8³(mod 11) = 6

8⁴(mod 11) = 4

8⁵(mod 11) = 10

8⁶(mod 11) = 3

8⁷(mod 11) = 2

8⁸(mod 11) = 5

8⁹(mod 11) = 7

8¹⁰(mod 11) = 1

       9:     9¹(mod 11) = 9.             The order of 9 is 5.

              9²(mod 11) = 4

              9³(mod 11) = 3

              9⁴(mod 11) = 5

              9⁵(mod 11) = 1

       10:    10¹(mod 11) = 10.           The order of 10 is 2.

              10²(mod 11) = 1

(d).

     All arithmetic statements are mod m.

We will show:  If s º t (1), then a^s = a^t.  We know a Î Z_n, and a is invertible with an order of m.

From (1), and the fact that m (mod m) = 0:

              s + m = t mod m.

     Write both sides as exponents of a:

                                  a^s+m = a^t

     By an exponent rule          a^s * a^m = a^t (2)

     The order of a is m, so a^m = 1.

     Simplify (2).                a^s * 1 = a^t

So, we can conclude that     a^s = a^t.

2.

     Here is the modulus table for multiplication mod 5.

From the table, we learn that the squares are: {0,1,4}.  These come from the highlighted cells.

Suppose that not every Pythagorean triple contains an element divisible by 5.  A zero indicates that a number is divisible by 5.  Suppose that there is not an element in every Pythagorean triple that is divisible by 5.  Then a²,b^2,c² Î {1,4}.  So, none of a²,b²,c² are zero.  But, one of a²,b²,c² must be zero in order to satisfy the Pythagorean relationship: a² + b² = c²_­­­­­­.  We can see this because if we choose two of the numbers in the equality, there is no possibility of satisfying the third one with a 1 or 4. This gives a contradiction.  A number mod 5 that equals zero is divisible by 5.  Therefore, one of a²,b²,c² must be divisible by 5.  If a number squared is divisible by 5, then the number is also divisible by 5.  From this, we conclude that one of a,b,c must be divisible by 5

3.

Assume a is invertible.  This means: $b½a * b º 1 (mod n).  So, n½a * b – 1 for some s. 

We can re-write this as:          a * b – n * s = 1 

When b = t and –n = C:       1 = a * t + n * s

By a theorem, the smallest positive linear combination is the gcd.  Since the gcd of a and n is expressed as a linear combination of s and t equal to 1, and because there is no other smaller positive integer than 1 available for a gcd, we conclude gcd(a,b) = 1.  By definition, two numbers that have a gcd of 1 are relatively prime.

Conversely, relatively prime means gcd(a,n) = 1

This leads to:          1 = a * t + n * s

Rearranging:            n * s = a * t – 1

Set t = b:              n * s = a * b – 1.

So, n½a * b – 1.  From this, we know that a * b º 1 (mod n).

From this, we can conclude that a is invertible.

Thus, we have shown that a is invertible iff a and n are relatively prime.

4.

     Choose p = 1050849, and q = 1219263.  We will compute

R₁₁(p­^q). 

Compute the mod 11 of p:         -1 + 0 – 5 + 7 – 0 + 8 – 4 + 9 = 14

-1 + 4 = 3

So, p mod 11 = 3.

Now, find the order of p:         3¹ mod 11 = 3^­­­­_­­­

                                                  3² mod 11 = 9^­­­­_­­­

                                                        3³ mod 11 = 5^­­­­_­­­

                                                        3⁴ mod 11 = 4^­­­­_­­­

                                                        3⁵ mod 11 = 1

The order of p is 5.

We know p º 3, so p⁵ = 3⁵.

The order of p is 5, so 3^5­­­­ º 1 (mod 11).  When we write p^q­­­, we notice that every 5 3s are congruent to 1. 

So, q mod 5 º 3, and 3³ º 5 = R₁₁(p­^q).