ps06 is the assignment filethe rest are class lecture notes & past hw for reference
21-127, Fall 2021, Carnegie Mellon University 21-127 Problem Sheet 6 The instructions for this problem sheet are on Canvas—please read them carefully. Solutions are due on Gradescope by 9:00pm ET on Thursday 21st October 2021. Q1–5 are worth 6 points each. To receive full credit, your solutions must be mathematically correct and complete, and should be written clearly enough that another student in the course would be able to easily and fully understand your arguments. 1. Let a,n ∈ Z with gcd(a,n) = 1, and let k be the order of a modulo n. Prove that k | ϕ(n). 2. Let p be a positive prime. (a) Let S = {b ∈ Z | 1 < b="">< p−="" 1}.="" prove="" that="" for="" all="" a="" ∈="" s,="" there="" exists="" a="" unique="" b="" ∈="" s="" such="" that="" ab≡="" 1="" mod="" p,="" and="" moreover="" b="" 6="a" for="" this="" value="" of="" b.="" (b)="" deduce="" from="" part="" (a)="" that="" (p−1)!≡−1="" mod="" p.="" 3.="" let="" x="{1,2,3,4}" and="" let="" y="[0,1]." for="" each="" of="" the="" following="" sets,="" determine="" whether="" it="" is="" the="" graph="" of="" a="" function="" from="" x="" to="" y="" .="" if="" it="" is,="" provide="" a="" formula="" for="" the="" function;="" if="" it="" is="" not,="" explain="" why.="" (a)="" {(1,0),(2,0),(3,0)}="" (b)="" {(a,0)="" |="" a="" ∈="" x}="" (c)="" {(0,="" i)="" |="" i="" ∈="" y}="" (d)="" {(1,0.1),="" (2,0.2),="" (3,0.3),="" (4,0.4)}="" (e)="" ∅="" (f)="" {(a,a2)="" |="" a="" ∈="" x}="" 4.="" a="" function="" g="" :="" r→r="" is="" said="" to="" be="" even="" if="" g(−x)="g(x)" for="" all="" x∈r,="" and="" a="" function="" h="" :="" r→r="" is="" said="" to="" be="" odd="" if="" h(−x)="−h(x)" for="" all="" x="" ∈="" r.="" (a)="" prove="" that,="" for="" all="" functions="" f="" :="" r→="" r,="" there="" exists="" a="" unique="" pair="" (g,h)="" of="" functions="" r→="" r="" such="" that="" g="" is="" even,="" h="" is="" odd,="" and="" f="" (x)="g(x)+h(x)" for="" all="" x="" ∈="" r.="" (b)="" let="" g="" :="" r→="" r="" be="" an="" even="" function="" and="" h="" :="" r→="" r="" be="" an="" odd="" function.="" for="" each="" of="" the="" functions="" g◦g,="" g◦h,="" h◦g="" and="" h◦h,="" determine="" whether="" it="" must="" be="" even="" or="" odd.="" 5.="" for="" each="" of="" the="" following="" sets,="" express="" it="" as="" an="" interval="" or="" as="" a="" union="" of="" intervals.="" (a)="" f∗[[−1,1]],="" where="" f="" :="" r→="" r="" is="" defined="" by="" f="" (x)="{" x2="" +1="" if="" x≥="" 0="" −x2="" if="" x="">< 0="" .="" (b)="" g∗[n],="" where="" g="" :r→r="" is="" the="" function="" defined="" for="" all="" x∈r="" by="" letting="" g(x)="" be="" the="" greatest="" even="" integer="" that="" is="" ≤="" x.="" there="" is="" no="" q6="" on="" this="" problem="" sheet="" 21-127="" lecture="" 19="" friday="" 15th="" october="" 2021="" example="" 1="" let="" x="" be="" the="" set="" of="" all="" inhabited="" finite="" subsets="" of="" n,="" and="" define="" f="" :="" x="" →="" n="" by="" f="" ({a1,a2,="" .="" .="" .="" ,an})="a1" for="" all="" {a1,a2,="" .="" .="" .="" ,an}="" ∈="" x="" .="" show="" that="" f="" is="" not="" well-defined="" by="" this="" specification,="" and="" explain="" how="" to="" modify="" it="" to="" make="" it="" well-defined.="" definition="" 2="" let="" f="" :="" x="" →="" y="" be="" a="" function.="" the="" graph="" of="" f="" is="" the="" subset="" gr(="" f="" )⊆="" x×y="" defined="" by="" example="" 3="" let="" f="" :="" {1,2,3}="" →="" {a,b,c,d}="" be="" defined="" by="" f="" (1)="a," f="" (2)="b" and="" f="" (3)="d," and="" let="" g="" :="" n→="" n="" be="" the="" function="" defined="" by="" g(n)="2n−1" for="" all="" n="" ∈="" n.="" express="" gr(="" f="" )="" in="" list="" notation,="" and="" gr(g)="" in="" implied="" list="" notation.="" 1="" axiom="" 4="" —="" function="" extensionality="" let="" f="" :="" x="" →="" y="" and="" g="" :="" a→="" b="" be="" functions.="" then="" f="g" if="" and="" only="" if="" the="" following="" conditions="" hold:="" (i)="" (ii)="" a="" consequence="" of="" the="" function="" extensionality="" axiom="" is="" that="" two="" functions="" with="" the="" same="" domain="" and="" codomain="" are="" equal="" if="" and="" only="" if="" their="" graphs="" are="" equal.="" definition="" 5="" let="" f="" :="" x="" →="" y="" and="" g="" :="" y="" →="" z="" be="" functions.="" the="" composite="" of="" f="" and="" g="" is="" example="" 6="" let="" f="" ,g,h="" :="" r→="" r="" be="" functions="" defined="" by="" f="" (x)="x2−4x+7," g(x)="√" x−3="" and="" h(x)="{" x="" if="" x=""> 0 −x if x < 0="" for="" all="" a="" ∈="" r.="" prove="" that="" (g◦="" f="" )(x)="h(x−2)" for="" all="" x="" ∈="" r.="" 2="" definition="" 7="" let="" x="" be="" a="" set.="" the="" identity="" function="" on="" x="" is="" the="" function="" idx="" :="" x="" →="" x="" defined="" by="" proposition="" 8="" —="" some="" properties="" of="" function="" composition="" (a)="" f="" ◦="" idx="f" =="" idy="" ◦="" f="" for="" all="" functions="" f="" :="" x="" →="" y="" ;="" (b)="" h◦="" (g◦="" f="" )="(h◦g)◦" f="" for="" all="" functions="" f="" :="" x="" →="" y="" ,="" g="" :="" y="" →="" z="" and="" h="" :="" z→w="" .="" proof="" �="" example="" 9="" prove="" that="" it="" is="" not="" true="" in="" general="" that="" f="" ◦g="g◦" f="" for="" all="" functions="" f="" :="" x="" →="" y="" and="" g="" :="" y="" →="" x="" .="" 3="" definition="" 10="" let="" f="" :="" x="" →="" y="" and="" let="" u="" ⊆="" x="" .="" the="" image="" of="" u="" under="" f="" is="" the="" subset="" f∗[u="" ]⊆="" y="" defined="" by="" the="" image="" of="" f="" is="" warning:="" strategy="" 11="" let="" f="" :="" x="" →="" y="" be="" a="" function,="" let="" u="" ⊆="" x="" and="" let="" y="" ∈="" y="" .="" in="" order="" to="" prove="" that="" y="" ∈="" f∗[u="" ],="" it="" suffices="" to="" example="" 12="" let="" f="" :="" n→="" n="" be="" defined="" by="" f="" (n)="n2" +1="" for="" all="" n="" ∈="" n.="" find="" f∗[{1,2,3,4}].="" 4="" 21-127="" lecture="" 18="" wednesday="" 13th="" october="" 2021="" recall="" from="" monday="" that="" the="" totient="" of="" an="" integer="" n="" is="" the="" number="" of="" elements="" of="" {1,2,="" .="" .="" .="" ,="" |n|}="" that="" are="" coprime="" to="" n—for="" example,="" ϕ(10)="4" since="" there="" are="" 4="" elements="" of="" {1,2,="" .="" .="" .="" ,10}="" that="" are="" coprime="" to="" 10,="" namely="" 1,3,7,9.="" theorem="" 1="" —="" euler’s="" theorem="" let="" a,n="" ∈="" z="" with="" gcd(a,n)="1." then="" idea="" of="" proof="" �="" 1="" example="" 2="" find="" the="" last="" two="" digits="" of="" 9123.="" theorem="" 3="" —="" fermat’s="" little="" theorem="" let="" p="" be="" a="" positive="" prime="" and="" let="" a="" ∈="" z.="" then="" proof="" �="" 2="" functions="" definition="" 4="" let="" x="" and="" y="" be="" sets.="" a="" function="" f="" from="" x="" to="" y="" is="" given="" x="" ∈="" x="" ,="" the="" element="" f="" (x)="" ∈="" y="" is="" called="" the="" of="" f="" at="" x.="" the="" set="" x="" is="" called="" the="" of="" f="" ,="" and="" the="" set="" y="" is="" called="" the="" of="" f="" .="" we="" denote="" the="" assertion="" that="" f="" is="" a="" function="" from="" x="" to="" y="" by="" we="" can="" specify="" a="" function="" by:="" •="" lists.="" •="" formulae.="" •="" cases.="" •="" algorithms.="" 3="" when="" specifying="" a="" function="" f="" :="" x="" →y="" ,="" we="" must="" be="" careful="" that="" the="" definition="" of="" a="" function="" is="" actually="" satisfied—namely:="" •="" totality.="" •="" existence.="" •="" uniqueness.="" when="" the="" specification="" of="" f="" truly="" does="" define="" a="" function,="" we="" say="" f="" is="" example="" 5="" let="" x="" be="" the="" set="" of="" all="" inhabited="" finite="" subsets="" of="" n,="" and="" define="" f="" :="" x="" →="" n="" by="" f="" ({a1,a2,="" .="" .="" .="" ,an})="a1" for="" all="" {a1,a2,="" .="" .="" .="" ,an}="" ∈="" x="" .="" show="" that="" f="" is="" not="" well-defined,="" and="" explain="" how="" to="" modify="" its="" definition="" to="" make="" it="" well-defined.="" 4="" 21-127="" lecture="" 20="" monday="" 18th="" october="" 2021="" recall="" from="" friday:="" definition="" 1="" let="" f="" :="" x="" →="" y="" and="" let="" u="" ⊆="" x="" .="" the="" image="" of="" u="" under="" f="" is="" the="" subset="" f∗[u="" ]⊆="" y="" defined="" by="" f∗[u="" ]="{y" ∈="" y="" |="" y="f" (x)="" for="" some="" x="" ∈u}="" the="" image="" of="" f="" is="" the="" subset="" f∗[x="" ]⊆="" y="" ,="" that="" is="" the="" set="" of="" all="" values="" of="" f="" .="" we="" now="" define="" the="" related="" notion="" of="" the="" preimage="" of="" a="" subset="" of="" the="" codomain="" of="" a="" function.="" definition="" 2="" let="" f="" :="" x="" →="" y="" and="" let="" v="" ⊆="" y="" .="" the="" preimage="" of="" v="" under="" f="" is="" the="" subset="" f="" ∗[v="" ]⊆="" x="" defined="" by="" example="" 3="" let="" f="" :n→n="" be="" defined="" by="" f="" (n)="n2+1" for="" all="" n∈n.="" find="" f="" ∗[v="" ],="" where="" v="{k∈N" |="" 16="" k6="" 10}.="" 1="" example="" 4="" let="" f="" :="" r→="" r="" be="" the="" function="" defined="" by="" f="" (x)="x2" for="" all="" x="" ∈="" r.="" find="" f∗[(1,2)]="" and="" f="" ∗[(1,4)]],="" expressing="" your="" answers="" as="" intervals="" or="" unions="" of="" intervals.="" 2="" proposition="" 5="" —="" order-preservation="" of="" image="" and="" order-reversal="" of="" preimage="" let="" f="" :="" x="" →="" y="" be="" a="" function,="" let="" a⊆="" b⊆="" x="" and="" let="" v="" ⊆w="" ⊆="" y="" .="" then="" (a)="" (b)="" proof="" �="" 3="" 21-127="" :="" problem="" sheet="" 4="" solutions="" thursday="" 7th="" october="" 2021="" 1.="" prove="" that="" r2="" \="" [(−∞,0)2∪="" (0,∞)2]="((−∞,0]×" [0,∞))∪="" ([0,∞)×="" (−∞,0])="" solution="" :="" some="" facts="" from="" definitions="" of="" set="" union="" and="" cartesian="" product="" :="" (1)="" x="" ∈="" a∪b="" ⇐⇒="" x="" ∈="" a="" ∨="" x="" ∈="" b="" (2)="" x="" ∈="" a∪b="" ⇐⇒="" x="" ∈="" a="" ∧="" x="" ∈="" b="" (3)="" (x,y)="" ∈="" a×b="" ⇐⇒="" x="" ∈="" a="" ∧="" y="" ∈="" b="" (4)="" (x,y)="" ∈="" a×b="" ⇐⇒="" x="" ∈="" a="" ∨="" y="" ∈="" b="" we="" prove="" the="" desired="" result="" by="" double="" containment="" :="" (part="" 1:⊆)="" let="" p="" ∈="" r2="" \="" [(−∞,0)2∪="" (0,∞)2].="" we="" can="" write="" p="(x,y)" for="" some="" x,y="" ∈="" r.="" by="" definition,="" (x,y)="" ∈="" (−∞,0)2∪="" (0,∞)2,="" so="" by="" fact="" (2),="" (x,y)="" ∈="" (−∞,0)2="" ∧="" (x,y)="" ∈="" (0,∞)2.="" then="" by="" fact="" (4),="" (="" x="" ∈="" (0,∞)="" ∨="" y="" ∈="" (0,∞)="" )︸="" ︷︷="" ︸="" cases="" 1,2="" ∧="" (="" x="" ∈="" (−∞,0)="" ∨="" y="" ∈="" (−∞,0)="" )︸="" ︷︷="" ︸="" subcases="" (i),(ii)="" .="" case="" 1:="" x="" ∈="" (0,∞)="" ⇐⇒="" x="" ∈="" (−∞,0].="" case="" 1-(i):="" x="" ∈="" (−∞,0).="" then="" x="0." let="" y="" ∈="" r.="" if="" y=""> 0 then (x,y) ∈ (−∞,0]× [0,∞) and if y < 0="" then="" (x,y)="" ∈="" [0,∞)×="" (−∞,0].="" case="" 1-(ii):="" y="" ∈="" (−∞,0).="" then="" y="" ∈="" [0,∞),="" so="" (x,y)="" ∈="" (−∞,0]×="" [0,∞).="" case="" 2:="" y="" ∈="" (0,∞)="" ⇐⇒="" y="" ∈="" (−∞,0].="" case="" 2-(i):="" x="" ∈="" (−∞,0).="" then="" x="" ∈="" [0,∞),="" so="" (x,y)="" ∈="" [0,∞)×="" (−∞,0].="" case="" 2-(ii):="" y="" ∈="" (−∞,0).="" then="" y="0." let="" x="" ∈="" r.="" if="" x="" 6="" 0="" then="" (x,y)="" ∈="" (−∞,0]×="" [0,∞)="" and="" if="" x=""> 0 then (x,y) ∈ [0,∞)× (−∞,0]. Thus in all subcases, we have p = (x,y) ∈ ((−∞,0]× [0,∞))∪ ([0,∞)× (−∞,0]). (Part 2:⊇) Let p ∈ ((−∞,0]× [0,∞))∪ ([0,∞)× (−∞,0]). Also, let p = (x,y) for x,y ∈ R