Solutions to MATH 356, Dr. Z. , Exam 2, Tue., Nov. 26, 2024 8:30-9:50am SEC-204

No Calculators! No Cheatsheets!

1. (10 pts.) Using the formula, find the unique x between 0 and 2001 such that

x ≡ 1 (mod 2) , x ≡ 5 (mod 7) , x ≡ 6 (mod 11) , x ≡ 4 (mod 13) .

Reminder (Chinese Remainder Theorem, General Version) If n_{1}, n_{2}, …, n_{k} are pairwise relatively prime (i.e. gcd(n_{i}, n_{j}) = 1, 1 ≤ i < j ≤ k), then the unique x , 0 ≤ x < n_{1} ⋯ n_{k} satisfying

x ≡ a_{i} (mod n_{i}) , 1 ≤ i ≤ k

is (letting N = n_{1} ⋯ n_{k})

x = ∑_{i=1}^{k} a_{i} \frac{N}{n_{i}} · ((\frac{N}{n_{i}})^{−1} (mod n_{i}))

Ans.: 1447

We have

x = 1 · (7 · 11 · 13) · ((7 · 11 · 13)^{−1} (mod 2)) + 5 · (2 · 11 · 13) · ((2 · 11 · 13)^{−1} (mod 7))

+6 · (2 · 7 · 13) · ((2 · 7 · 13)^{−1} (mod 11)) + 4 · (2 · 7 · 11) · ((2 · 7 · 11)^{−1} (mod 13))

= 1 · (1001) · ((1001)^{−1} (mod 2)) + 5 · (286)) · (286^{−1} (mod 7))
+6 · (182) · ((182)^{−1} (mod 11)) + 4 · (154) · ((154)^{−1} (mod 13))
= 1 · (1001) · ((1)^{−1} (mod 2)) + 5 · (286)) · ((−1)^{−1} (mod 7))
+6 · (182) · (6^{−1} (mod 11)) + 4 · (154) · ((−2)^{−1} (mod 13))

By inspection

6^{−1} (mod 11) = 2 , 2^{−1} (mod 13) = 7 ,

Hence

x = 1 · (1001) · (−1) + 5 · (286) · (−1) + 6 · (182) · 2 + 4 · (154) · (−7) =

(1001−1430+2184−4312) (mod 2002) = (1001−1430+182−308) (mod 2002) = 1447 .

2. (10 pts.) What is the day of the week of Nov. 26, 3024. Reminders: Every year that is a multiple of 4 is a leap year, with the exception that every year that is a multiple of 100 is not a leap year, with the exception to the exception that if the year is a multiple of 400 it is a leap year.

Ans.: Friday

There are 1000 years from now, and 250 − 10 + 2 = 242 leap years. Today is day 3 so

3 + 1000 + 242 (mod 7) = 3 + 6 + 4 (mod 7) = 13 (mod 7) = 6 .

3. a (5 pts.) What is is the remainder when you divide 102! by 103? Explain! What theorem are you using?

Ans.: −1 alias 102

Wilson’s theorem claims that if p is a prime then (p − 1)! (mod p) = −1. Since 103 is a prime, this follows. b (5 pts.) What is is the remainder when you divide 11^{1002} by 1003? What theorem are you using?

Ans.: 1

Pascal’s identity says

a^{p−1} (mod p) = 1 ,

if a ≠ 0. Since 1003 is a prime, it follows.

4. a (3 pts.) Define Euler’s Toitent function ϕ(n). ϕ(n) is the numebr of positive integers less than n that are relatively prime to n. b (7 pts. altogether) State (2 pts.) and prove (5 pts), Euler’s Classical Formula for Euler’s Toitent function ϕ(n). (a)

∑_{d|n} ϕ(d) = n

(b) Write all the n fractions with denominator n and numerators from 1 to n

\frac{1}{n}, \frac{2}{n}, …, \frac{n}{n}

Now reduce them so that the top and bottom are relatively primes. The denominators that show up at the bottom are all divisors of n, and for each such divisor d, all the integers relatively prime to d show up. There are ϕ(d) of them. Adding them up gives n.

5. (10 pts.) Using the RSA encrypton method, with p = 5 , q = 11 , e = 7 , Alice sent you the encripted message c = 2 what was her original message m?

Ans.: m = 8

n = 5 · 11 = 55, ϕ(n) = (5 − 1) · (11 − 1) = 40; gcd(7, 40) = 1, so e = 7 is an OK key. We need to find d

d = 7^{−1} (mod 4)0 = 23

(either by trial-and-error or the Extended Euclidean algorithm applied to gcd(40, 7)

40 = 5 · 7 + 5 ; 5 = 40 − 5 · 7
7 = 1 · 5 + 2 ; 2 = 7 − 5 = 6 · 7 − 40
5 = 2 · 2 + 1 ; 1 = 5 − 2 · 2 == 40 − 5 · 7 − 2(6 · 7 − 40) = 340 − 177

Taking mod 40

7^{−1} (mod 4)0 = −17 (mod 40) = 23

So

m = c^{23} (mod 4)0 = 2^{23} (mod 40)
2^{1} = 2 ; 2^{2} = 4 ; 2^{4} = 16 ; 2^{8} = 16^{2} (mod 4)0 = 16 ;
2^{16} = 16^{2} (mod 4)0 = 16 ;

Hence

2^{23} (mod 4)0 = 2^{16+4+2+1} (mod 4)0 = 16 · 16 · 4 · 2 (mod 4)0 = 8 .

6. (10 pts., 2 pts. each) What are σ(105), σ_{2}(105), σ_{3}(105), σ_{4}(105), σ_{5}(105)?

Ans.: σ(105) = 192 σ_{2}(105) = (1 + 3^{2})(1 + 5^{2})(1 + 7^{2}) = 13000, σ_{3}(105) = (1 + 3^{3})(1 + 5^{3})(1 + 7^{3}) σ_{4}(105) = (1 + 3^{4})(1 + 5^{4})(1 + 7^{4}) σ_{5}(105) = (1 + 3^{5})(1 + 5^{5})(1 + 7^{5})

The prime factorization of 105 is

105 = 3 · 5 · 7 .

7. (10 pts., 5 pts. each) Find (a): μ(2002) (b): μ(4004). Explain!

Ans.: (a) 1 a: b: 0

2002 = 2 · 7 · 11 · 13 is a product four distinct primes, hence μ(2002) = (−1)^{4} = 1 4004 = 2^{2} · 7 · 11 · 13 is not a product of distinct primes, hence μ(4004) = 0 8. (10 pts.) Is 17 a quadratic residue modulo 281? Explain!

Reminders: Rule 1: If p is an odd prime and a and b are not multiples of p, then

(\frac{ab}{p}) = (\frac{a}{p}) · (\frac{b}{p})

Rule 2: If p is an odd prime then

(\frac{−1}{p}) = (−1)^{(p−1)/2} .

Rule 3: If p is an odd prime then

(\frac{2}{p}) = (−1)^{(p^{2}−1)/8} .

Rule 4: (THE QUADRATIC-RECIPROCITY LAW) If p and q are distinct odd primes, then

(\frac{p}{q}) (\frac{q}{p}) = (−1)^{(p−1)(q−1)/4} .

Ans.: Yes; 17 is a quadratic residue of 281.

(\frac{17}{281}) (\frac{281}{17}) = (−1)^{280)(16)/4} = 1 But 281 (mod 1)7 = 9, hence (\frac{17}{281}) (\frac{9}{17}) = 1 So

(\frac{17}{281}) = (\frac{9}{17}) = (\frac{3 · 3}{17}) == (\frac{3}{17})^{2} = 1 .

Since the Legendre symbol (\frac{p}{q}) is either 1 or −1 its square is always 1. So we don’t need

to know (\frac{3}{17})

9. (10 pts.) For the following partitions λ, (i) Draw the Ferrers graph (ii) Find the conjugate partition λ′.

λ = (7, 5, 5, 3, 2, 1, 1, 1)

(i)

\begin{matrix}∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ \\ ∗ & ∗ & ∗ & ∗ & ∗ \\ ∗ & ∗ & ∗ & ∗ & ∗ \\ ∗ & ∗ & ∗ \\ ∗ & ∗ & ∗ \\ ∗ \\ ∗ \\ ∗ \end{matrix} .

(ii) (8, 5, 4, 3, 3, 1, 1)

10. (10 pts. altogether)

i. (5 pts) Apply Glashier’s bijection (in the distinct → odd direction) to the distinct partition (8, 6, 3, 2, 1) to get an partition, call it μ

8 = 8cdot1 ; 6 = 2 · 3 ; 3 = 1 · 3 ; 2 = 2 · 1 ; 1 = 1 · 1 .

This becomes 1^{8}, 3^{2}, 3^{1}, 1^{2}, 1^{1} Combining, we get 1^{11}3^{3} and in the usual notation

μ = (3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

ii. (5 pts.) Apply Glashier’s bijection (in the odd → distinct direction) to the partition μ and show that you get (8, 6, 3, 2, 1) back, as you should.

(3^{3}, 1^{11}) = (3^{2+1}, 1^{8+2+1}) = (6, 3.8, 2, 1)

Putting it in order, we get that indeed the reverse mapping gives (8, 6, 3, 2, 1)