31.4 Solving modular linear equations

31.4-1

Find all solutions to the equation \(35x \equiv 10 \pmod{50}\).

\(\\{6, 16, 26, 36, 46\\}\).

31.4-2

Prove that the equation \(ax \equiv ay \pmod n\) implies \(x \equiv y \pmod n\) whenever \(\gcd(a, n) = 1\). Show that the condition \(\gcd(a, n) = 1\) is necessary by supplying a counterexample with \(\gcd(a, n) > 1\).

Since \(ax \cdot x' + n \cdot y' = d\),

we have

31.4-3

Consider the following change to line 3 of the procedure \(\text{MODULAR-LINEAR-EQUATION-SOLVER}\):

C++
1	3 x0 = x'(b / d) mod (n / d)

Will this work? Explain why or why not.

Assume that \(x_0 \ge n / d\), then the largest solution is \(x_0 + (d - 1) \cdot (n / d) \ge d \cdot n / d \ge n\), which is impossible, therefore \(x_0 < n / d\).

31.4-4 \(\star\)

Let \(p\) be prime and \(f(x) \equiv f_0 + f_1 x + \cdots + f_tx^t \pmod p\) be a polynomial of degree \(t\), with coefficients \(f_i\) drawn from \(\mathbb Z_p\). We say that \(a \in \mathbb Z_p\) is a zero of \(f\) if \(f(a) \equiv 0 \pmod p\). Prove that if \(a\) is a zero of \(f\), then \(f(x) \equiv (x - a) g(x) \pmod p\) for some polynomial \(g(x)\) of degree \(t - 1\). Prove by induction on \(t\) that if \(p\) is prime, then a polynomial \(f(x)\) of degree \(t\) can have at most \(t\) distinct zeros modulo \(p\).

(Omit!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用