CSC3001 Assignment 2 Solution

Instructions:
1. Print out this question paper (two-sided) and write down your full working on the blank area.
2. You can have discussions with your classmates. However, make sure all the solutions you submit are your own work. Any plagirism will be given ZERO mark.
4. Before your submission, please make a softcopy of your work for further discussion in a tutorial.
5. After making your softcopy, submit your assignment to the dropbox located on the 4th floor in Chengdao Building.
Student Number: Name:
1. (20 points) Let p be an odd prime. Prove that there are exactly integers a ∈ {1,...,p − 1} such that x2 ≡ a (mod p) for some x.


2. (20 points Suppose that n3 unit cubes are stacked into a large n × n × n cube. Let x,y,z ∈ Zn and label each unit cube by (x,y,z) with respect to its location (see the picture for n = 3).

The unit cubes (x,y,z) and (x0,y0,z0) are adjacent if one of the following conditions holds:
• x0 − x ≡ ±1 (mod n) and y0 = y,z0 = z; or
• |y0 − y| ≡ 1 (mod n) and x0 = x,z0 = z; or
• |z0 − z| ≡ 1 (mod n) and x0 = x,y0 = y.
For each n ∈ Z+, provide an ordering of all the unit cubes satisfying the following:
• every two consecutive cubes are adjacent;
• the last cube and the first cube in the list are adjacent.

3. (20 points Let n ∈ N be with n ≥ 2. Let k ∈ {1,2,...,n − 1} be a fixed number such that gcd(k,n) = 1. Given the balls labeled by 1,2,...,n − 1, we try to color each ball black or white such that
(1) i and n − i are of the same color;
(2) for each i 6= k, we have i and |i − k| are of the same color.
Prove that all the balls are of the same color.

4. (20 points Let Tn denote the number of different ways that a convex polygon with n + 2 sides can be cut into triangles by connecting vertices with non-crossing line segments. (For example, Tn = 14 for n = 4 as shown below)

Find the recurrence relation of Tn and hence find the closed form of Tn using generating functions.


5. (20 points) Consider the linear congruence
17x ≡ 9 (mod 276)
(a) Show that this congruence has a unique solution.
(b) Show that the given congruence and the following system have the same solution.
 x ≡ 0

x ≡ 1
17x ≡ 9 (mod 3)
(mod 4)
(mod 23)
(c) Solve the original congruence without assistance of calculator.

6. (10 points) [bonus question] ”A computer is to a number theorist, like a telescope is to an astronomer. It would be a shame to teach an astronomy class without touching a telescope; likewise, it would be a shame to teach this class without telling you how to look at the integers through the lens of a computer.” - William Stein, Number Theorist
Consider a perfect number, defined as a positive integer n such that it is equal to the sum of all its positive divisors, excluding n itself. Denoting the sum of positive divisors of n by σ(n), then a perfect number has the property that
σ(n) − n = n
Denoting the k-th perfect number by Pk, we have
P1 = 6, P2 = 28, P3 = 496, P4 = 8128
Based on the above patterns, there were some early conjectures regarding perfect numbers:
A. the n-th perfect number contains exactly n digits; and B. the even perfect numbers end, alternately, in 6 and 8; and
C. there is no odd perfect number.
By means of a computer program, disprove the first two of these conjectures by finding and examining the fifth and the sixth perfect number. The third conjecture remains an open problem.