Question

Lemma 8.1 Let n be a positive integer, and let s and t be integers. Then the following hold. (i) We have s et mod n if and only if n dividest - s. (ii) We have pris + t) = Hn (s) +Mn(t) mod n. (iii) We have Hr(st) = Hn (3) Men(t) mod n. Proof. The definition of fr gives us integers u, v such that S = nu + An (8) and t = nu+ Het). (i) Assume first that set mod n. Then, by definition, Hr(s) = Hn(t). Thus, t-s = nu + n(t) - nu - Hn(s) = nv – nu = n(v – u). Thus, by definition, n divides t-s. Assume now, conversely, that n divides t-s. Then, by Lemma 5.1(i), n divides t-s+n(u – v) = t - nv - (s – nu) = n(t) – Hr(s). Thus, as An(t) € N, and An(s) N., An($) = n(t), and that means that s at mod n. (ii) The definition of Mr gives us an integer w such that s+t = nw +(s+t). Thus, nw + Hn(s + t) = nu + Mn() + nv + Mn(t) = n(u + v) + Mne () + Mn(t), so that n(w – u – v) = Hn (s) + Men(t) – Hn(s+t). 38 This shows that n divides An (8) + An(t) – Men(8 +t). Thus, by (i), M(8 +t) = Mr (8) + Hn () mod n.

I need help to prove iii.

Answer 1

iii)

$\mu _n(st)=\mu _n(s).\mu _n(t)modn$

the detennation of $\mu _n$ gives us an integer w

such that

s.t =nw + $\mu _n$ (st)

thus nw +$\mu _n$(st)= nu + nv + $\mu _n$ (s).$\mu _n$(t)

n(w-u-v)=$\mu _n$(s).$\mu _n$(t)-$\mu _n$(s.t)

this shows that n divides $\mu _n$ (s).$\mu _n$(t)-$\mu _n$(s.t)

thus $\mu _n$ (s.t)=$\mu _n$(s)$\mu _n$(t)mod n

Please give thumbs up, I need your support.