2022/4/28 21:25 HW #10 (SP22): CMPSC 360 SP 22, Section 01: Discrete Math/Cs
HW #10 (SP22)
截止时间 4月14日 23:59 得分 96 问题 9
可用 4月7日 22:00 至 4月14日 23:59 7 天 时间限制 无
Copyright By PowCoder代写 加微信 powcoder
此测验锁定于 4月14日 23:59。
最新 尝试 1 1,732 分钟 79，满分 96 分 *
* 有些问题尚未计分
正确答案已隐藏。
此测验的分数: 79，满分 96 分 * 提交时间 4月14日 23:51 此尝试进行了 1,732 分钟。
Solve the congruence
https://psu.instructure.com/courses/2172592/quizzes/4483759?module_item_id=35273921 1/8
2022/4/28 21:25 HW #10 (SP22): CMPSC 360 SP 22, Section 01: Discrete Math/Cs
Solve the congruence 55x ≡ 34 (mod 89) and find all possible values of x.
https://psu.instructure.com/courses/2172592/quizzes/4483759?module_item_id=35273921 2/8
2022/4/28 21:25 HW #10 (SP22): CMPSC 360 SP 22, Section 01: Discrete Math/Cs
Fill in the following information as though it were part of a Chinese Remainder Theorem problem:
1) If N = 105 and we knew = 5, = 7, then =
15 and = 1 (find the smallest
possible positive y value here).
Treat part 2 as a completely separate question:
2) If we had a system of 3 modulus equations set up as a CRT problem where (assuming all the given information is true):
7 11 7 4 10 15
Do not simplify your x value, leave it as the pure sum of multiplication of proper terms.
Then x = 1625
https://psu.instructure.com/courses/2172592/quizzes/4483759?module_item_id=35273921 3/8
2022/4/28 21:25 HW #10 (SP22): CMPSC 360 SP 22, Section 01: Discrete Math/Cs
Using Fermat’s Little Theorem find 32003 mod 455.
incorrect approach
答案 3: 1625
https://psu.instructure.com/courses/2172592/quizzes/4483759?module_item_id=35273921 4/8
2022/4/28 21:25 HW #10 (SP22): CMPSC 360 SP 22, Section 01: Discrete Math/Cs
We chose two prime numbers p = 17, q = 11, and e = 7. Calculate d and show the public and private keys.
Please show all your work.
A message was encrypted using shift cipher f(p) = (p+10) mod 26. The encrypted message was : DSWO PYB PEX
If you decrypt it, what do you see?
Note: Write the exact deciphered message. If the decrypted message is THANK YOU, enter exactly “THANK YOU”.
TIME FOR FUN
https://psu.instructure.com/courses/2172592/quizzes/4483759?module_item_id=35273921 5/8
2022/4/28 21:25 HW #10 (SP22): CMPSC 360 SP 22, Section 01: Discrete Math/Cs
Given p = 37 and q = 43, can we choose d = 71? If yes, justify your answer, otherwise suggest one value for d.
Then compute the public and the private keys.
Solve the system:
Hint: First solve each of the linear congruences separately, and then use the Chinese Remainder
Theorem to solve simultaneously.
https://psu.instructure.com/courses/2172592/quizzes/4483759?module_item_id=35273921 6/8
2022/4/28 21:25 HW #10 (SP22): CMPSC 360 SP 22, Section 01: Discrete Math/Cs
83mod210 188mod210
(Optional)
A) Suppose we have two numbers b1, b2 such that b1 ≡ b2 mod p for some integer p.
https://psu.instructure.com/courses/2172592/quizzes/4483759?module_item_id=35273921 7/8
2022/4/28 21:25 HW #10 (SP22): CMPSC 360 SP 22, Section 01: Discrete Math/Cs
测验分数: 79，满分 96 分
Prove that for every polynomial of degree n with integer coefficients f (x), we have f (b1) ≡ f (b2) mod p.
Hint: prove that for every term like akxk in the polynomial f (x) this property holds and then
conclude that it holds for the summation of all terms which is equal to f (x) = anxn + an−1xn−1 +… + a1x + a0.
To achieve this sub-goal, prove the following:
• b1 ≡ b2 mod p ⇒ b1 + c ≡ b2 + c mod p for arbitrary integer c.
• b1 ≡ b2 mod p ⇒ cb1 ≡ cb2 mod p for arbitrary integer c.
• b1 ≡ b2 mod p ⇒ b1k ≡ b2k mod p for a positive integer k.
B) We know that a number is divisible by 9 if and only if the sum of its digits is divisible by
9. Apply the result of the previous section to prove the correctness of this rule. Then generalize
your result and show that we can derive a similar rule for n − 1 when we are representing a
number in base n. That is, if a have number (a1a2…ak)n which is represented in base n, we have
a2 +…+ak.
n − 1|(akak−1…a1)n ⇔ n − 1|a1 +
https://psu.instructure.com/courses/2172592/quizzes/4483759?module_item_id=35273921 8/8
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com