K power residues and primitive roots - Trying to solve x^k congruent to a (mod m), m > 0, (a,m) =3D 1 - b and c are 2 solutions * b and c must differ by a "Kth root of unity" * There is some b* such that bb* congruent to 1 (mod m) * c =3D bb*c =3D bd, with d =3D b*c * Since c^k congruent to a (mod m), c^k congruent to (b^k)(d^k) (mod = m) * Therefore, there is some d^k congruent to 1 (mod m) Definition: If (a,m) =3D 1, the "order of a (modulo m)" is the smallest = positive integer h with the property that a^h congruent to 1 (mod m). = This is most often indicated by h =3D ord a, or h =3D ord[m] a. 1 =B2 = ord[m] a =B2=CAphi(m). Theorem (6.2) - Let m > 0, (a,m) =3D 1 - (i) For any s, a^s congruent to 1 (mod m) iff ord[m] a | s - (ii) a^s congruent to a^t (mod m) iff s congruent to t (mod ord[m] = a) Proof of (i) - Let h =3D ord[m] a, and suppose that s =3D hk for some k - a^s congruent to (a^h)^k congruent to 1^k congruent t 1 (all mod m) - Therefore, a^s congruent to 1 (mod m) - Suppose that a^s congruent to 1 (mod m) - Use the division algorithm to write s =3D hq + r, 0 =B2=CAr < h - a^s congruent to 1 means that a^(hq + r) congruent to 1 (mod m) - Simply to a^r congruent to 1, which means that r =3D 0 (as h is the = smallest which otherwise satisfies the property) - Therefore, h | s Proof of (ii) - Suppose s =B3 t, so a^s =3D (a^(s - t))a^t - a^s congruent to a^t means that a^(s-t) congruent to 1 (mod m) - ord[m] a | (s - t) by (i) - s congruent to t (mod ord[m] a) Example - m =3D 72 - phi(m) =3D 24 - ord[72] a =3D 1, 2, 3, 4, 6, 8, 12, or 24 - Finding ord[72] 5 - 5^1 not congruent to 1 (mod 72) - 5^2 not congruent to 1 (mod 72) - 5^3 not congruent to 1 (mod 72) - 5^6 congruent to 1 (mod 72), so the order can't be 4 (as doesn't = divide 6) - Therefore, ord[72] 5 =3D 6 Theorem (6.3) - Let m > 0, (a,m) =3D 1, d =3D ord[m] a - (i) ord[m] a^k =3D d/(d,k) for any k - (ii) if e | d, then ord[m] a^e =3D d/e Proof - Note: (ii) is just a special case of (i) - Suppose (a^k)^j congruent to 1 (mod m) for some j - a^kj congruent to 1 (mod m), so we use Theorem 6.2 - d | kj iff d/(d,k) | j - Therefore, ord[m] a^k =3D d/(d,k) Theorem - Let h =3D ord[m] a, k =3D ord[m] b - Suppose (h,k) =3D 1 - ord[m] ab =3D hk - More generally, we can find an integer c with ord[m] c =3D [h,k] Proof - Suppose r =3D ord[m] ab - (ab)^r congruent to 1 (mod m) - Congruence with a and b yields r | hk - We can then show that hk | r, so hk =3D r. Definition: Let m > 0. The "least universal exponent" of m is the = smallest positive integer u such that a^u congruent to 1 (mod m) for all = (a,m) =3D 1. Definition: We say that g is a "primitive root" of m if ord[m] g =3D = phi(m).= --Apple-Mail-3-527333497 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; x-unix-mode=0644; name="[MA490]7-13-04.txt" Content-Disposition: attachment; filename="[MA490]7-13-04.txt" x^5 congruent to 9 (mod 14) x^5k congruent to 3^2 (mod 14) 6 is a primitive root of 14 5k congruent to 2 (mod 6) = --------------------------------------------------------------------------= ---- Legendre's Theorem ------------------ Every prime has a primitive root Proof ----- Let u be the universal exponent of p, u =B2=CAp-1 (Fermat's Theorem). = x^4 congruent to 1 (mod p) has exactly p-1 solutions. By Lagrange's = Theorem, x^4 congruent to 1 (mod p) has at most u solutions, so u =B3=CAp-= 1. Therefore, u =3D p-1. Therefore, there is some g with p not = dividing g and ord[p] g =3D p-1. = --------------------------------------------------------------------------= ---- Theorem 6.8 ----------- If (a,m) =3D 1, then a is a primitive root of m iff a^((phi(m))/q) not = congruent to 1 (mod m) for any q | phi(m) Example ------- Show that 5 is a primitive root of 23 phi(23) =3D 22 =3D 2*11 Show that 5^2 not congruent to 1 (mod 23) and 5^11 not congruent to 1 = (mod 23) Example ------- Is 2 a primitive root of 29? phi(23) =3D 28 =3D 2*2*7 2^4 not congruent to 1 (mod 29), 2^14 not congruent to 1 (mod 29) Proof ----- If a is a primitive root, then by definition phi(m) =3D ord a and since = 1 =B2=CA(phi(m))/q < phi(m) for all primes q | phi(m) we have = a^(phi(m)/q) not congruent to 1 (mod m). d | phi(m), so phi(m) =3D dk for some k. If d < phi(m), then k > 1, so = let q | k be a prime. Then a^(phi(m)/q) =3D a^(dk/q) =3D (a^d)^(k/q) = congruent to 1 (mod m), which contradicts our assumption. Therefore, ord[m] a =B3=CAphi(m), so ord[m] a =3D phi(m). If g is a primitive root of prime p, then g^((p-1)/2) not congruent to 1 = (mod p). Therefore, it is a quadratic non-residue modulo p. Lucas' Theorem -------------- m > 1 and suppose there is an integer a with a^(m-1) congruent to 1 (mod = m) and a^((m-1)/q) not congruent to 1 (mod m) for any prime q | m-1. = Then m is a prime. If g is a primitive root of m, then g^s congruent to g^t (mod m) iff s = congruent to t (mod phi(m)). g^k is a primitive root iff ord[m] g^k =3D phi(m) Theorem ------- Suppose that g is a primitive root of m. Then, g^k is a primitive root = of m iff (phi(m), k) =3D 1. Example ------- We know that 5 is a primitive root of 23 (k,22) =3D 1, so k =3D 1, 3, 5, 7, 9, 13, 15, 17, 19, 21 Therefore, 5^1, 5^3, etc., which reduce to 5, 10, 20, 17, 11, 21, 19, = 15, 7, 14= --Apple-Mail-3-527333497 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; x-unix-mode=0644; name="[MA490]7-14-04.txt" Content-Disposition: attachment; filename="[MA490]7-14-04.txt" Office hours today are cancelled, tomorrow are usual (11-12) plus = 2:30-3:30 = --------------------------------------------------------------------------= ---- Primitive roots --------------- If m > 0, g is a primitive root of m if ord[m] g =3D phi(m). Suppose we know m has a primitive root. Then, {g, g^2, ... g^(phi(m))} = is a reduced residue system modulo m. Theorem ------- If m > 0 and g is a primitive root for m, then g^k is a primitive root = as long as (phi(m),k) =3D 1. Example ------- 3 is a primitive root of 14 so 3 and 3^5 are the two primitive roots of = 14. Theorem ------- If m has primitive roots, then it must have phi(phi(m)) primitive roots. Theorem 6.14 ------------ Suppose g is a primitive root of m, and d | phi(m). ord[m] g^k =3D d = iff k is of the form j(phi(m)/d), with (j,d) =3D 1. Therefore, there = are phi(d) elements of order d. Proof ----- =46rom Theorem 6.3 (part i), (a,m)=3D1 and ord[m] a =3D s =3D> ord[m] = a^k =3D s/(s,k). ord[m] g =3D phi(m), (phi(m),k) =3D phi(m)/d, k =3D = j(phi(m)/d). Note that (k,phi(m)/d) =3D (j(phi(m)/d),d(phi(m)/d) =3D = (phi(m)/d)(j,d), so (j,d) must be 1 in order to have it equal to = phi(m)/d. Notation -------- m has some primitive root g, and we're solving x^k congruent to a (mod = m) with (a,m) =3D 1. Then, a congruent to g^i (mod m) for some 1 =B2=CAi = =B2=CAphi(m). i is called the "index" of a (with bas g). Theorem ------- Let g be a primitive root of m, with indices following having base g. (i) ind(1) congruent to 0 (mod phi(m)), ind(g) congruent to 1 (mod = phi(m)) (ii) a congruent to b (mod phi(m)) iff ind(a) congruent to ind(b) (mod = phi(m)) (iii) ind(ab) congruent to ind(a) + ind(b) (mod phi(m)) (iv) ind(a^k) congruent to k ind(a) (mod phi(m)) Example ------- Working mod 19, primitive root is 2 a ind(a) -------------- 1 18 2 1 3 13 4 2 5 16 6 14 7 6 8 3 9 8 10 17 11 12 12 15 13 5 14 7 15 11 16 4 17 10 18 9 Start at 2, putting in 1. =46rom there, multiply by 2, reduce if = necessary (mod 19), putting consecutive values after that. Theorem 6.18 ------------ Let m>0 and suppose m has a primitive root. If (a,m) =3D 1, then x^k = congruent to a (mod m) has a solution iff a^((phi(m))/(k,phi(m))) = congruent to 1 (mod m). Note: This is a generalization of Euler's = Criterion. Proof ----- Let g be a primitive root of m and set d =3D (k,phi(m)). Note: x^k = congruetn t a (mod m) iff k ind(x) congruent to ind(a) (mod phi(m)). = Let y =3D ind(x). So, ky congruent to b (mod phi(m)) has a solution iff = d | b. x =3D g^y iff d | ind(a). d | ind(a) iff a^(phi(m)/d) congruent = to 1 (mod m), which happens if (phi(m)/d)(ind(a)) congruent to 0 (mod = phi(m)), which means that d | ind(a). Definition ---------- If(a,m) =3D 1, we say that a is a "Kth power residue" (modulo m) if x^k = congruent to a (mod m) is solvable. Otherwise, it's a Kth power = non-residue. Corollary --------- If p is prime and p doesn't divide a, then a is a Kth power residue (mod = p) iff a^((p-1)/(k,p-1)) congruent to 1 (mod p). Note: x^k congruent to 1 (mod m) always has solutions. So, if m has a = primitive root there are always (k,phi(m)) solutions. Theorem ------- If k | phi(m) and m has a primitive root, then x^k congruent to 1 (mod = m) has k solutions. Corollary --------- If m has a primitive root, then there are phi(m)/(k,phi(m)) Kth power = residues mod m. Proof ----- a is a Kth power residue (mod m). a^((phi(m))/(k,phi(m)) congruent to 1 = (mod m). But by the last theorem, there are phi(m)/(k,phi(m)) solutions = to x^((phi(m))/(k,phi(m)) congruent to 1 (mod m).= --Apple-Mail-3-527333497 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; x-unix-mode=0644; name="[MA490]7-15-04.txt" Content-Disposition: attachment; filename="[MA490]7-15-04.txt" How to use indices: 8x^4 congruent to 3 (mod 19)? x^4 congruent to 17 (mod 19)? Solvable only if 17^(phi(19)/(4,phi(m))) congruent to 1 (mod m) 17^9 congruent to 1 (mod m)? 17 congruent to 2^10 (mod m) due to index of 10 2^90 congruent to 1 (mod m)? x^4 congruent to 2^10 (mod 19) x congruent to 2^k (mod 19), k =3D ind(x) 4 ind(x) congruent to 10 (mod 18) 4k congruent to 10 (mod 18) 2k congruent to 5 (mod 9) k congruent to 7 (mod 18) or k congruent to 16 (mod 18) Go to index table, look up 7 and 16 x congruent to 14 (from k congruent to 7) or x congruent to 5 (both = mod 19) Example ------- 5x^7 congruent to 4 (mod 19)? 5 + 7 ind(x) congruent to 2 (mod 18) 7 ind(x) congruent to 15 (mod 18) ind(x) congruent to 13*15 (mod 18) ind(x) congruent to 15 (mod 18) x congruent 12 (mod 19), as taken off the index table Theorem ------- Suppose p is an odd prime and g is a primitive root modulo p. (i) If g^(p-1) not congruent to 1 (mod p^2), then g is a primitive root = for p^2. If g^(p-1) congruent to 1 (mod p^2), g+p is a primitive root = mod p^2. (ii) If k =B3 2 and g is a primitive root for p^k, the g is a primitive = root for p^(k+1). Proof ----- (i) Let h =3D ord[p^2] g for some prime p. Then, g^h congruent to 1 = (mod p^2), meaning g^h congruent to 1 (mod p). (p-1) | h, since g is a = primitive root. Also, h | phi(p^2), so h | p(p-1). Either h =3D p(p-1) = or h =3D p-1. If h =3D p(p-1), then g is a primitive root of p^2. g+p = congruent to g (mod p), so g + p is a primitive root of p. Suppose that = (g+p)^(p-1) congruent to 1 (mod p^2). Therefore, by Binomial Theorem, = (g+p)^(p-1) =3D p^(p-1) + (p-1)pg^(p-2) + a bunch of other terms that = are divisible by p^2. Therefore, (g+p)^(p-1) congruent to p^(p-1) + = (p-1)pg^(p-2) (mod p^2). Reduction results in 1 congruent to 1 + = p(p-1)g^(p-1) (mod p^2), so p | g (which is a contradiction as g is a = primitive root), so therefore (g+p)^(p-1) CANNOT be congruent to 1 (mod = p^2), meaning g+p is a primitive root of p^2. (ii) Suppose k =B3=CA2 and g is a primitive root of p^2. Let h =3D = ord[k+1] g. Then, h | phi(p^(k+1)), so h | (p-1)p^k. g^h congruent to = 1 (mod p^(k+1)), so g^h congruent to 1 (mod p^k), so phi(p^k) | h, so = (p-1)p^(k-1) | h. Show that either h =3D (p-1)p^k or h =3D (p-1)p^(k-1) = and that h =3D (p-1)p^(k-1) is impossible. Checking this: 2^18 congruent to 1 (mod 19^2)? 2^18 congruent to 58 (mod 361), so 2 is a primitive root (mod 19^k) for = all k Theorem ------- Let p be an odd prime and g a primitive root of p^k. If g is odd, g is = a primitive root of 2p^k. If g is even, the g + p^k is a primitive root = of 2p^k. Proof ----- If g is odd, g^a congruent to 1 (mod 2) for any a, so g^a congruent to 1 = (mod 2p^k) iff g^a congruent to 1 (mod p^k). ord[p^k] g =3D phi(p^k), = ord[2p^k] g =3D phi(p^k). phi(2p^k) =3D phi(2) phi(p^k) =3D phi(p^k). = So, ord[2p^k] g =3D phi(2p^k), so g is primitive. If g is even, it = can't be primitive as (g,2p^k) =3D 2. g+p^k is odd, g+p^k congruent to = g (mod p^k), so g+p^k is an odd primitive root of p^k, and hence a = primitive root of 2p^k.= --Apple-Mail-3-527333497 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; x-unix-mode=0644; name="[MA490]7-16-04.txt" Content-Disposition: attachment; filename="[MA490]7-16-04.txt" #15 --- ord[103] 5 =3D 102, so ord[103] 5^2 =3D 102/(2,102) =3D 51 =AD 102, so = not primitive 5^102 congruent to 1 (mod 103), so (5^2)^51 congruent to 1 (mod 103). = Thus, ord[103] 5^2 =3D 51, 51 =AD=CA102, so not primitive. 25 =3D 5^2, meaning (25\103) =3D 1, so it can't be primitive. #9 -- All must be congruent mod 2^k, (k,100) =3D 20, so 2^20, 2^40, etc. = Least positive residues are 95, 36, 87, 84, and 101. #4 -- ord[41] 9 =3D 4, ord[41] 10 =3D 5, (4,5) =3D 1, so ord[41] 90 =3D 20. = 90 congruent to 8 (mod 41), so ord[41] 8 =3D 20. = --------------------------------------------------------------------------= ---- Theorem 6.25 (Gauss) -------------------- The only integers with primitive roots are 1, 2, 4, p^k and 2p^k, prime = p > 2. Proof ----- If m =3D 1, 2, 4, p^k, 2p^k, we have seen that they have primitive = roots. If m has a primitive root, then x^2 congruent to 1 (mod m) must = have exactly 2 solutions. If m =3D 2^k p[1]^k[1] p[2]^k[2]... = p[r]^k[r], then by Theorem 5.5 x^2 congruent to 1 (mod m) has 2^r = solutions if k =3D 0 or 1, 2^(r+1) solutions if k =3D 2, and 2^r+2 = solutions if k =B3 3. This can only be a primitive root when r=3D1 or = r=3D0, so to have a primitive root for m we must have it be of the form = 2p^k for some prime p and some integer k (via r=3D1) or 2^2 (via r=3D0). = --------------------------------------------------------------------------= ---- #7 -- g is a primitive root of p, ord[p] g =3D p-1, so (p-1)/(p-1,k) =3D 4. = Thus, (p-1,k) =3D (p-1)/4, so p congruent to 1 (mod 4). #24 --- (-7)^k =3D (7)^k for 2 | k, so we check odd factors of phi(241) =3D 240. = Finding none which cause (-7)^k congruent to 1 (mod 241), -7 is a = primitive root. Alternately, 7^120 congruent to -1 (mod 241) and the = others are distinct, so no odds can be congruent -1, meaning that there = can't be any congruent 1 (before 240).= --Apple-Mail-3-527333497 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; x-unix-mode=0644; name="[MA490]6-14-04.txt" Content-Disposition: attachment; filename="[MA490]6-14-04.txt" HW: --- * Read p.6-11 * p.32 #1, 2, 4, 5, 8, 12 = --------------------------------------------------------------------------= ---- Pythagorean Triples - 3 non-zero integers (a,b,c) such that a^2 + b^2 =3D c^2 - Classification * Reductions + a > 0, b > 0, c > 0 + Primitive Pythagorean Triple (PPT) =3D A Pythagorean Triple for = which a, b, and c have no common factors (not a PPT if, for any k =AD 0, = (ka)^2 + (kb)^2 =3D (kc)^2) * Parity + If a and b are both even, so is c (which would make it not = primitive) + If a and b are both odd, c is even a =3D 2x + 1, b =3D 2y + 1, c =3D 2z (2x + 1)^2 + (2y + 1)^2 =3D (2z)^2 4x^2 + 4x + 4y^2 + 4y + 2 =3D 4z^2 4(x^2 + x + y^2 + y) + 2 =3D 4z^2 Impossible, since left-hand side (LHS) has remainder 2 when = divisible by 4 but RHS is divisible by 4 (so a and b both can't be odd) + Therefore, a is odd, b is even, and c is odd * Factorization a^2 =3D c^2 - b^2 a^2 =3D (c - b)(c + b) To show that (c - b) and (c + b) are both squares, it is enough to = show (ETS) that (c - b) and (c + b) have no common factors. Suppose = that d is a common factor. That means that d is a factor of (c + b) - = (c - b) as well as (c + b) + (c - b), i.e. 2b and 2c. However, due to = a^2 + b^2 =3D c^2, b and c cannot have a common factor aside from 2, but = c is odd. Therefore, there is no common factor. (c - b) =3D t^2, (c + b) =3D s^2 for some integers s > t =B3 1 c =3D (s^2 + t^2)/2, b =3D (s^2 - t^2)/2, a^2 =3D s^2 t^2, a =3D = st Theorem: Every PPT is formed by a =3D st, b =3D (s^2 - t^2)/2, c =3D = (s^2 + t^2)/2, where s > t =B3 1 are any odd integers. = --------------------------------------------------------------------------= ---- Divisibility - Definition + a and b are integers (which may be abbreviated as Z) with a =AD 0 + a divides b if b =3D aq for some q in Z + Symbolized as a | b for "a divides b" Theorem 1.2 (a, b, c in Z) - If a | b, a | kb for any k in Z - If a | b and b | a, a =3D =B1b - If a | b and b | c, a | c - If a | b and a | c, a | (sb + tc) for any s and t in Z - For any k =AD 0, a | b iff ka | kb Proof of Theorem 1.2 - b =3D aq for some q in Z kb =3D k(aq) =3D a(kq) So a | kq - a | b and b | a, b =3D aq, a =3D bt b =3D aq =3D btq tq =3D 1 t, q =3D =B11 So b =3D =B1a Theorem 1.3 (a, b in Z, a > 0) - There exist unique integers q and r with 0 =B2 r < a and b =3D aq + = r Well Ordering Principle =3D there is a smallest element in any non-empty = set of non-negative integers (as 0 is the floor for the set). Proof of Theorem 1.3 - S =3D {n =B3 0 | n =3D b - qt for some t} r is the smallest number in S r =3D b - aq for some r 0 =B2 r < a Suppose r > a =3D> r - a > 0 (b - aq) - a > 0 b - a(q + 1) > 0 r - a is in S, which is a contradiction to r being the smallest in = S Suppose b =3D aq[1] + r[1] =3D aq[2] + r[2], 0 =B2 r[i] < a r[1] > r[2] =3D> a > r[1] > r[1] - r[2] > 0 r[1] - r[2] =3D a(q[2] - q[1]), which is impossible as no multiple = ak of a satisfies the requirement that a > ak > 0, so r[1] =B2 r[2] and = r[2] =B2 r[1], so therefore r[1] =3D r[2], so q[1] =3D q[2] (quotients = and remainders are unique) = --------------------------------------------------------------------------= ---- Greatest Common Divisor - a > 0, b > 0 in Z - The largest positive integer dividing both a and b is the GCD - Symbolized as (a, b) Theorem 1.4 (a, b in Z, d =3D (a, b)) - d is the smallest positive integer which can be expressed in the = form of as + bt such that s and t are in Z= --Apple-Mail-3-527333497 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; x-unix-mode=0644; name="[MA490]6-15-04.txt" Content-Disposition: attachment; filename="[MA490]6-15-04.txt" Theorem of Euclid - Given (a, b) =3D 1, a | bc - Now know a | c Least Common Multiple (LCM) is denoted by [a, b] Theorem 1.13: if a and b are not zero, ab =3D [a, b](a, b) Primes - Definition: an integer p > 1 such that its only factors are 1 and = itself - Lemma 1.15: if p is prime, p | ab, p | a or p | b - Lemma: if p | a1*a2*a3*..., p | ai for some i Fundamental Theorem =3D every integer n > 1 can be expressed uniquely = (up to order) as a product of primes (as in n =3D p1^r1 * p2^r2 * = p3^r3...) WLOG =3D Without Loss Of Generality Theorem 1.17 a =3D p1^a1 * p2^a2 * ... pr^ar, b =3D p1^b1 * p2^b2 * ... pr^br, ai =B3= 0, bi =B3=CA0 --- (a, b) =3D p1^m1 * p2^m2 * ... pr^mr, mi =3D min (ai, bi) [a, b] =3D p1^M1 * p2^M2 * ... pr^Mr, Mi =3D max (ai, bi) = --------------------------------------------------------------------------= ---- Theorem There are infinitely many primes --- Assume that p1, p2, ... pk are all distinct primes n =3D p1 * p2 * ... pk + 1 n cannot be divided by any primes p1, p2, ... pk and must be divided = by some prime pm, which causes a contradiction Euclidean Algorithm m, n =AD 0 (m, n) =3D (n, m - nt) for any t= --Apple-Mail-3-527333497 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; x-unix-mode=0644; name="[MA490]6-16-04.txt" Content-Disposition: attachment; filename="[MA490]6-16-04.txt" Due Friday: p. 32 #6, 13, 17, 18, 22, 31, 32 p. 64 #1, 2, 3, 4, 6, 7 = --------------------------------------------------------------------------= ---- Find (a,b), given that a > b > 0 --- a =3D bq + r r =3D a - bq (a, b) =3D (b, a - bq) =3D (b, r) r[0] =3D a, r[1] =3D b r[0] =3D r[1]q[1] + r[2] r[1] =3D r[2]q[2] + r[3] r[2] =3D r[3]q[3] + r[4] ... r[k] =3D r[k+1]q[k+1] + 0 Therefore, (a, b) =3D r[k+1] when the final r[k+2] =3D 0 (a, b) =3D as + bt, s and t in Z Example: (1848, 1368) 1848 =3D 1*1368 + 480 1368 =3D 2*480 + 408 480 =3D 1*408 + 72 408 =3D 5*72 + 48 72 =3D 1*48 + 24 48 =3D 2*24 + 0 So (1848, 1368) =3D 24 24 =3D 72 - 48 =3D 72 - (408 - 5*72) =3D 6*72 - 408 =3D 6*480 - 7*408 =3D 20*480 - 7*1368 =3D 20*1848 - 27*1368 The linear combination resulting in the GCF is 20*1848 - 27*1368 = --------------------------------------------------------------------------= ---- First example of Diophantine Equation Solving ax + by =3D c with a, b, and c in Z Find x, y in Z satisfying the equation Let d =3D (a, b) If ax + by =3D c, then by Theorem 1.2, d | c If not d | c, there are no solutions c =3D dk for some k in Z d =3D as + bt for some s and t in Z c =3D (as + bt)k c =3D ask + btk c =3D ax* + by* ax + by =3D c =3D ax* + by* a(x - x*) =3D b(y* - y) (a/d)(x - x*) =3D (b/d)(y* - y) (a/d, b/d) =3D 1 (a/d) | (y* - y) y* - y =3D (a/d)u for some u in Z (a/d)(x - x*) =3D (b/d)(a/d)u x - x* =3D (b/d)u x =3D x* + (b/d)u and y =3D y* - (b/d)u for some u in Z Theorem 1.24: a, b, and c in Z and d =3D (a, b) If not d | c, ax + by =3D c has no solutions If d | c, ax + by =3D c has infinite solutions Further, if there is a solution x*, y* then any other solution is of the = form x =3D x* + (b/d)u, y =3D y* - (a/d)u Suppose a, b, c > 0, can assume (a, b) =3D 1 x*, y* is any fixed solution x > 0, y > 0 x* + bu > 0 y* - au > 0 x* > -bu u > -x*/b y* > au u < y*/a -x*/b < u < y*/a Theorem 1.25: The number of positive solutions to ax + by =3D c is the = number of integers u with -x*/b < u < y*/a and x*, y* any fixed solution There are at least n solutions if c > nab = --------------------------------------------------------------------------= ---- Congruence - a and b are congruent modulo m if m | (b - a) - Symbolized as a, then triple-lines, then b - Sometimes specified as "b is a residue of a mod m" - 0 =B2 b < m =3D> we say that b is the "least non-negative residue of = a mod m" - {b0, b1, b2, ... bm} is a complete set of residues mod m if for = every a in Z, a is congruent to bi (mod m) for some i - Example: {7, -4, 15, 10, 5, -12} is a complete set of residues mod = 6 Theorem 2.2 - If a is congruent to b (mod m) then b is congruent to a (mod m) - If a is congruent to b (mod m) and b is congruent to c (mod m), then = a is congruent to c (mod m) - If a is congruent to b (mod m) and c is congruent to d (mod m), then = a =B1 c is congruent to b =B1 d (mod m) - If a is congruent to b (mod m), then ca is congruent to cb (mod m) - For any common divisor c of a, b, and m, a is congruent to b (mod m) = iff a/c is congruent to b/c (mod m/c) - If ca is congruent to cb (mod m), then a is congruent to b (mod = m/(m, c)). .. thus, if c and m are relatively prime, then a is = congruent to b (mod m)= --Apple-Mail-3-527333497 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; x-unix-mode=0644; name="[MA490]6-17-04.txt" Content-Disposition: attachment; filename="[MA490]6-17-04.txt" NO CLASS TOMORROW! HW: --- * Make sure HW for Tues/Wed/Thur done (and done CAREFULLY) for Monday * HW for Fri/Mon due on Tuesday = --------------------------------------------------------------------------= ---- Theorem 2.3: m > 0, a, b, c, d in Z (i) If a is congruent to b (mod m) and c is congruent to d (mod m), then = ac is congruent to bd (mod m) (ii) If a is congruent to b (mod m), for any n =B3 0, a^n is congruent = to b^n (iii) If a is congruent to b (mod m), for any polynomial f(x) with = coefficients in Z, f(a) is congruent to f(b) (mod m) Proof of (i) a is congruent to b (mod m) c is congruent to d (mod m) Theorem 2.2 gives us ac congruent to bc (mod m), bc congruent to bd = (mod m) Transitivity gives us ac congruent to bd (mod m) Proof of (ii) Apply (i) n times Proof of (iii) Apply (ii) along with Theorem 2.2 Theorem 2.4: Suppose d | m, d > 0 (i) If a is congruent to b (mod m), then a is congruent to b (mod d) (ii) If a is congruent to b (mod m1) and a is congruent to b (mod m2), = then a is congruent to b (mod [m1, m2]) (iii) If a is congruent to b (mod mi) for 1 =B2 i =B2 r, a is congruent = to b (mod [m1, m2, ... mr]) = --------------------------------------------------------------------------= ---- Divisibility Tests - 2 | n iff 2 | a[0], where a[0] is the last digit in n - 3 | n iff 3 | (a[k] + a[k-1] + ... + a[0]) - 9 | n iff 9 | (a[k] + a[k-1] + ... + a[0]) - 2^r | n iff 2^r divides the number formed by the last r digits - 11 | n iff 11 divides the alternating sum of digits (a[0] - a[1] + = ....) S is a solution to ax congruent to b (mod m) if aS is congruent to b = (mod m) If S is a solution and S' is congruent to S (mod m), S' is also a = solution d =3D (a, m), ax congruent to b (mod m) has a solution d | b, in which = case there are d incongruent solutions mod m If x* is any fixed solution, then all solutions are of the form x =3D x* = + (m/d)t, 0 =B2 t =B2 d - 1 with x* a fixed solution of (a/d)x congruent = to (b/d) (mod m/d)= --Apple-Mail-3-527333497 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; x-unix-mode=0644; name="[MA490]6-21-04.txt" Content-Disposition: attachment; filename="[MA490]6-21-04.txt" HW: --- * Get stuff ready to turn in tomorrow! * Read p.44-46, do p.64 #11, 27, 32, 36, 37 (due Friday) * Tomorrow: read p.46-48, do p.64 #8, 25, 33, 40, 43, 44 (due Friday) * Wednesday: read p.71-73 (3.3), do p.94 #1, 2, 6, 8 (due Friday) * Thursday: read p.73-74 (3.6), do p.94 #10, 11, 12, 13, 15 (due = Tuesday) * Friday: read p.74-76 (due Tuesday) * Go to office hours today (2:30) = --------------------------------------------------------------------------= ---- Theorem (d =3D (a, m)) ax congruent to b (mod m) is solvable iff d | b. In this case, there = are exactly d incongruent solutions mod m, given by x =3D x* + (m/d)t, 0 = =B2 t < d - 1 with x* a fixed solution of (a/d)x congruent to (b/d), mod = m/d. Example: 15x congruent to 9 (mod 24) a =3D 15, b =3D 9, m =3D 24 d =3D 3, so exactly 3 solutions exist 3 =3D 15s + 24t 9 =3D 3(15s + 24t) =3D 15(3s) + 24(3t) 15 =3D 1 * 9 + 6 9 =3D 1 * 6 + 3 6 =3D 2 * 3 + 0 3 =3D 2(24) - 3(15) 9 =3D 6(24) - 9(15) 9 congruent to 9(15), mod 24 x* congruent to 9 mod 24 Corollary If a and m are relatively prime, ax congruent to b (mod m) has a = single unique solution (as (a, m) =3D 1, so d =3D 1). ax congruent to 1 (mod m) has a solution, with x an inverse of a Techniques to solve ax congruent to b (mod m) 1.) Euclidean Algorithm (d =3D (a, m), d | b, d =3D as + mt) 2.) Reduce coefficients mod m 3.) If m is a prime, multiply by nearest integer to m / a, use = residues of least absolute value = --------------------------------------------------------------------------= ---- Chinese Remainder Theorem (I) Suppose that (m, n) =3D 1. For any b,c there is a solution to the = system: x congruent to b (mod n) x congruent to c (mod m) There is a unique such x with 0 =B2 x < mn To solve: Use first congruence to determine form of x, plug into next Example: x congruent to 8 (mod 11) x congruent to 3 (mod 19) x =3D 8 + 11y 8 + 11y congruent to 3 (mod 19) 11y congruent to 14 (mod 19) 77y congruent to 98 (mod 19) y congruent to 3 (mod 19) Chinese Remainder Theorem (II) Let m1, m2, ... mr be positive integers with the property that (mi, = mj) are relatively prime for all i and j. Let a1, a2, ... ar in Z, and = m =3D m1m2...mr, there is a unique solution mod m to the system x = congruent to a1 mod m1, x congruent to a2 mod m2, ... x congruent to ar = mod mr.= --Apple-Mail-3-527333497 Content-Transfer-Encoding: 7bit Content-Type: text/plain; x-unix-mode=0644; name="[MA490]6-22-04.txt" Content-Disposition: attachment; filename="[MA490]6-22-04.txt" Finding the day of the week (1900-1999) - Gregorian Calendar (1582 AD) - Julian Calendar (before 1582) - Gregorian almost universally accepted immediately, though England and its colonies didn't adopt until 1752 - 365 days, except +1 every 4 years, but not if div. by 100 but not 400 - Work modulo 7, with numbers for days (0 for Saturday, 1 for Sunday, etc.), month codes (J1 F4 M4 A0 M2 J5 O1 N4 D6) Example: Nov. 22, 1963 1.) Divide last two digits by 4, take quotient => 15, which is 1 mod 7 2.) Add last two digits (63) to this residue => 1 + 63, which is 1 mod 7 3.) Add to this the day of the month (22) => 1 + 22, which is 2 mod 7 4.) Add the month code (4) => 2 + 4, which is 6 mod 7 5.) Since it wasn't in January or Feb. of a leap year, don't subtract 1 Therefore, it was a Friday For 2000-2099, subtract 1 For 1800-1899, add 2 For 1700-1799, add 4 For 1600-1699, add 6 For 1582-1599, add 0 ------------------------------------------------------------------------------ Try: April 30, 1983 1.) Divide last two digits by 4, take quotient => 20, which is 6 mod 7 2.) Add last two digits (83) to this residue => 6 + 83, which is 5 mod 7 3.) Add to this the day of the month (30) => 5 + 30, which is 0 mod 7 4.) Add the month code (0) => 0 + 0, which is 0 mod 7 5.) Since it wasn't in January or Feb. of a leap year, don't subtract 1 Therefore, it was a Saturday ------------------------------------------------------------------------------ Lemma 3.1 Suppose p is an odd prime, p doesn't divide a, some b with b^2 congruent to a (modulo p), then there are exactly two solutions to x^2 congruent to a mod p --Apple-Mail-3-527333497 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; x-unix-mode=0644; name="[MA490]6-23-04.txt" Content-Disposition: attachment; filename="[MA490]6-23-04.txt" Webpage is coming soon - Syllabus - Assignments - Phone/email list - Announcements Evening study session - Thursdays 7-10PM - If possible, will be in MATH 731 (otherwise, likely on the second = floor) - Prof. Goldberg won't necessarily be in his office, but might Midterm exam - July 8th, 7-9PM - 1 hour exam, but 2 hours to do = --------------------------------------------------------------------------= ---- Lemma 3.1 (from last time) Let p be an odd prime, suppose p doesn't divide a. If there is an = integer b such that b^2 congruent to a (mod p), then the congruence x^2 = congruent to a (mod p) has exactly two incongruent solutions. In fact, = they are x congruent to b (mod p) and x congruent to -b (mod p). Analogous result for real numbers If x^2 =3D a has a solution and a =AD 0, then there are two solutions = (which are x =3D =C3a and x =3D -=C3a). The reason why p is prime is that when squaring its least residues, one = cannot get the same number (as that would cause there to be only a = single solution). Theorem 3.2 (Dirichlet-inspired) Let p be any prime, and 1=B2a=B2p-1. If x^2 congruent to a (mod p) = has no solution, then (p-1)! is congruent to a^((p-1)/2) (mod p). If = x^2 congruent to a (mod p) has a solution, then (p-1)! is congruent to = -(a^((p-1)/2)) (mod p). Wilson's Theorem Let p be a prime. (p-1)! is congruent to -1 (mod p). Corollary 3.4 (Euler's Criterion) Let p be prime and p doesn't divine a. x^2 congruent to a (modulo p) = is solvable if a^((p-1)/2) congruent to 1 (modulo p) and is not solvable = if a^((p-1)/2) congruent to -1 (modulo p). Theorem 3.5 Let p be an odd prime. x^2 congruent to -1 (mod p) has a solution if = p congruent to 1 mod 4 and no solution if p congruent to 3 (mod 4).= --Apple-Mail-3-527333497 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; x-unix-mode=0644; name="[MA490]6-24-04.txt" Content-Disposition: attachment; filename="[MA490]6-24-04.txt" Study room - MATH731, Thursdays from 7-10PM = --------------------------------------------------------------------------= ---- Question regarding Julian calendar shift (will provide more info later) Question from homework (3*26! is what mod 29?) 3*26! congruent to x (mod 29) 3*28! congruent to (27)(28)x (mod 29) .... = --------------------------------------------------------------------------= ---- Fermat's Little Theorem Let p be a prime. Then, for any a in Z, a^p is congruent to a (mod = p). Alternately, if p doesn't divide a, a^(p-1) congruent to 1 (mod p). Looking for prime divisors of 2^p - 1 Lemma 3.7 Let a, u, v, m in Z, u > 0, v > 0, m > 0, d =3D (u,v). If a^u = congruent to 1 (mod m) and a^v congruent to 1 (mod m), a^d congruent to = 1 (mod m). Theorem 3.8 Suppose q is a prime number which divides 2^p - 1, for some odd prime = p. Then, q congruent to 1 (mod 2p). Example 2^7 - 1. p =3D 7. What possible q divides 2^7 - 1? q =3D 14k + 1 No primes q exist such that q =B2 =C3p 127 is prime Theorem 3.9 Let p be a prime, and suppose p doesn't divide a. Let n be the = smallest positive number with p dividing a^n - 1. Then, n divides p - = 1.= --Apple-Mail-3-527333497 Content-Transfer-Encoding: base64 Content-Type: text/plain; x-unix-mode=0644; name="[MA490]6-25-04.txt" Content-Disposition: attachment; filename="[MA490]6-25-04.txt" /v8ASABXADoACgAtAC0ALQAKACoAIABSAGUAZABvACAAbABhAHMAdAAgAGgAbwBtAGUAdwBvAHIA awAgAHMAZQBjAHQAaQBvAG4AIAAoAHAALgA5ADQAIAAjADEAMAAsACAAMQAxACwAIAAxADIALAAg ADEAMwAsACAAMQA1ACkAIABmAG8AcgAgAFQAdQBlAHMAZABhAHkALgAuAC4AIABiAGUAIABjAGEA cgBlAGYAdQBsACAAYQBiAG8AdQB0ACAAdQBzAGUAIABvAGYAIAPGAAoAKgAgAEMAbwBuAHQAaQBu AHUAZQAgAHcAaQB0AGgAIAByAGUAcwB0ACAAbwBmACAAaABvAG0AZQB3AG8AcgBrAAoACgAtAC0A LQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAt AC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0A LQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAKAAoAcAAuADkANAAgACMAMQAy AAoALQAtAC0ALQAtAC0ALQAtAAoAIAAgAHgAXgAyADAAMAAgAC0AIAAyADAAMAB4ACAAYwBvAG4A ZwByAHUAZQBuAHQAIAB0AG8AIAAwACAAKABtAG8AZAAgADEAOQA5ACkACgAgACAAeABeADIAMAAw ACAALQAgAHgAIABjAG8AbgBnAHIAdQBlAG4AdAAgAHQAbwAgADAAIAAoAG0AbwBkACAAMQA5ADkA KQAKACAAIAB4ACgAeABeADEAOQA5ACAALQAgADEAKQAgAGMAbwBuAGcAcgB1AGUAbgB0ACAAdABv ACAAMAAgACgAbQBvAGQAIAAxADkAOQApAAoAIAAgAFMAaQBuAGMAZQAgADEAOQA5ACAAaQBzACAA cAByAGkAbQBlACwAIABlAGkAdABoAGUAcgAgAHgAIABjAG8AbgBnAHIAdQBlAG4AdAAgAHQAbwAg ADAAIAAoAG0AbwBkACAAMQA5ADkAKQAgAG8AcgAgACgAeABeADEAOQA5ACAALQAgADEAKQAgAGMA bwBuAGcAcgB1AGUAbgB0ACAAdABvACAAMAAgACgAbQBvAGQAIAAxADkAOQApACwAIABtAGUAYQBu AGkAbgBnACAAZQBpAHQAaABlAHIAIAB4ACAAYwBvAG4AZwByAHUAZQBuAHQAIAB0AG8AIAAwACAA bwByACAAeAAgAGMAbwBuAGcAcgB1AGUAbgB0ACAAdABvACAAMQAgACgAYgBvAHQAaAAgAG0AbwBk ACAAMQA5ADkAKQAKAAoALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0A LQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAt AC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0ALQAtAC0A CgAKAG0AIAA+ACAAMQAsACADxgAoAG0AKQAgAGkAcwAgAHQAaABlACAAbgB1AG0AYgBlAHIAIABv AGYAIABpAG4AdABlAGcAZQByAHMAIABrACAAdwBpAHQAaAAgADEAICJkACAAawCgImQAoABtAC0A MQAsACAAYQBuAGQAIAAoAGsALABtACkAIAA9ACAAMQAuACAAIABGAG8AcgAgAGMAbwBuAHYAZQBu AGkAZQBuAGMAZQAsACADxgAoADEAKQAgAD0AIAAxAC4ACgAKAFIAZQBkAHUAYwBlAGQAIAByAGUA cwBpAGQAdQBlACAAcwB5AHMAdABlAG0AIABpAHMAIABhACAAcgBlAHMAaQBkAHUAZQAgAHMAeQBz AHQAZQBtACAAdwBoAGkAYwBoACAAbwBuAGwAeQAgAGMAbwBuAHQAYQBpAG4AcwAgAHQAaABvAHMA ZQAgAGkAbgB0AGUAZwBlAHIAcwAgAHQAaABhAHQAIABhAHIAZQAgAHIAZQBsAGEAdABpAHYAZQBs AHkAIABwAHIAaQBtAGUAIAB0AG8AIAB0AGgAZQAgAG0AbwBkAHUAbAB1AHMALgAKAAoAVABoAGUA bwByAGUAbQAgADMALgAxADMAIAAoAEUAdQBsAGUAcgAnAHMAIABUAGgAZQBvAHIAZQBtACkACgAg ACAARgBvAHIAIABhAG4AeQAgAG0AIAA+ACAAMAAsACAAaQBmACAAKABhACwAbQApACAAPQAgADEA LAAgAHQAaABlAG4AIABhAF4DxgAoAG0AKQAgAGMAbwBuAGcAcgB1AGUAbgB0ACAAdABvACAAMQAg ACgAbQBvAGQAIABtACkALgAKAAoATABlAG0AbQBhACAAMwAuADEAMgAKACAAIABMAGUAdAAgAG0A PgAwACwAIABhAG4AZAAgAHMAdQBwAHAAbwBzAGUAIAB7AHIAWwAxAF0ALAAgAHIAWwAyAF0ALAAg AC4ALgAuACAAcgBbA8YAKABtACkAXQB9ACAAaQBzACAAYQAgAHIAZQBkAHUAYwBlAGQAIAByAGUA cwBpAGQAdQBlACAAcwB5AHMAdABlAG0AIABtAG8AZAB1AGwAbwAgAG0ALgAgACAASQBmACAAKABh ACwAbQApACAAPQAgADEALAAgAHQAaABlAG4AIAB7AGEAcgBbADEAXQAsACAAYQByAFsAMgBdACwA IAAuAC4ALgAgAGEAcgBbA8YAKABtACkAXQB9ACAAaQBzACAAYQBsAHMAbwAgAGEAIAByAGUAZAB1 AGMAZQBkACAAcgBlAHMAaQBkAHUAZQAgAHMAeQBzAHQAZQBtACAAbQBvAGQAdQBsAG8AIABtAC4A CgAKAEMAbwByAG8AbABsAGEAcgB5AAoAIAAgAEkAZgAgACgAYQAsAG0AKQAgAD0AIAAxACwAIABh AF4AKAPGACgAbQApAC0AMQApACAAaQBzACAAYQAgAG0AdQBsAHQAaQBwAGwAaQBjAGEAdABpAHYA ZQAgAGkAbgB2AGUAcgBzAGUAIABmAG8AcgAgAGEALAAgAG0AbwBkAHUAbABvACAAbQAuAAoACgPG ACgAbQBuACkAIAA9ACADxgAoAG0AKQAgACoAIAPGACgAbgApACAAaQBmACAAKABtACwAbgApACAA PQAgADEALg== --Apple-Mail-3-527333497--