Question

6.32 Theorem. If k and n are natural numbers with (k, d(n)) =I, then there exist positive integers u and v satisfving ku=(n)u The previous theorem not only asserts that an appropriate exponent is always availahle, but it also tells us how to find it. The numbers u and are solutions lo a lincar Diophantine cquation just like those we studied in Chapter 6.33 Exercisc. Use your observations so far to find solutions to the follow ing congruences. Be sure lo check that your answers are indeed solutions 1. 4 (mod 11) (mod 18) 2. x= 3. x=2 (mod 8) You have probably devised a method for finding a solution to a congru- ence of the form x*b (mod n), hut the third congruence in the above excrcise shows that this method does not al ways work 6.34 Question. What hypotheses on k, h, and n for wour method to produce a solution to the congruence xr do you think are necessary (mod n)? Make a conjecture and prove it 6.35 Theorem. Ifb is an integer and k and n ane natural mumbers such that (k, (n)) =1 and (b, n)= 1, then x =b (mod ) has a unique solution modulo n. Moreover that solution is given by x (mod n), (n) +1 where u and u are positive integers such that ku Our experiments at the beginning of the soction showed that a number can have multiple roots modulo another numher. But the previous theorem asserts that under the given hypotheses, our method not only finds a kth root modulo , but in lact finds the only kth root 6.36 Exercise. Find the 49th root of 100 modulo 151. The following two theorems assert that for squure-frec numbers n, that is, numbers that are products of distinet primes, the hypothesis (b, n) 1 from Theorem 6.35 can be dropped. The first theorem is a generalization of Theurem 5.2.

Answer 1

Gomod n) hure 1o . hehanet saue fo Zu -loV = 1 elearly p3, --2 te u=3,V:3ill Le a sautiog (mo3 1) .. dera 4mod ,3 isauton 5 311 mod 18) hane to salve fr 5u -6V z 1 : uz-1, V--1 ha sahhn anod 8) T a- nt .. Сиod в) 2 Scann with CamScanner