(* Content-type: application/vnd.wolfram.mathematica *)

(*** Wolfram Notebook File ***)
(* http://www.wolfram.com/nb *)

(* CreatedBy='Mathematica 10.0' *)

(*CacheID: 234*)
(* Internal cache information:
NotebookFileLineBreakTest
NotebookFileLineBreakTest
NotebookDataPosition[       158,          7]
NotebookDataLength[     34268,        800]
NotebookOptionsPosition[     32681,        745]
NotebookOutlinePosition[     33039,        761]
CellTagsIndexPosition[     32996,        758]
WindowFrame->Normal*)

(* Beginning of Notebook Content *)
Notebook[{
Cell[TextData[{
 StyleBox["MAT 331:",
  FontSize->24],
 " ",
 StyleBox["Homework 4",
  FontSize->24]
}], "Section",
 CellChangeTimes->{{3.618884780257655*^9, 3.618884795191327*^9}, {
   3.619013741815179*^9, 3.619013742915434*^9}, {3.6190639773624067`*^9, 
   3.6190639931423893`*^9}, 3.6190640316767807`*^9, {3.620115017220894*^9, 
   3.620115018260913*^9}, {3.622348203306175*^9, 3.622348203752513*^9}, {
   3.7017871936620502`*^9, 3.701787194395801*^9}}],

Cell[CellGroupData[{

Cell[TextData[StyleBox["Problem 4.1", "Subsection"]], "Section",
 CellChangeTimes->{{3.6188834470493517`*^9, 3.618883458254191*^9}, {
  3.6188841737965927`*^9, 3.618884177712782*^9}, {3.6188846295181627`*^9, 
  3.6188846297983932`*^9}, {3.619056965231044*^9, 3.619056965742797*^9}, {
  3.620184812387269*^9, 3.620184812898695*^9}, {3.620185327776074*^9, 
  3.620185327888328*^9}, {3.622348234232251*^9, 3.622348237600342*^9}, {
  3.623068761984556*^9, 3.6230687632311697`*^9}, {3.701787196531636*^9, 
  3.701787197051684*^9}}],

Cell[TextData[{
 "Let n be a positive integer. Euler\[CloseCurlyQuote]s totient function ",
 StyleBox["\[Phi](n)",
  FontWeight->"Bold"],
 " gives the number of positive integers less than or equal to n which are \
relatively prime to n.  In this exercise you will prove that ",
 StyleBox["\[Phi]",
  FontWeight->"Bold"],
 " is given by the formula ",
 Cell[BoxData[
  FormBox[
   StyleBox[
    RowBox[{
     RowBox[{"\[Phi]", "(", "n", ")"}], "=", 
     RowBox[{"n", "*", 
      RowBox[{
       RowBox[{
        RowBox[{"(", 
         RowBox[{"1", "-", 
          StyleBox[
           FractionBox["1", 
            SubscriptBox["p", "1"]],
           FontSize->18]}], ")"}], 
        RowBox[{"(", 
         RowBox[{"1", "-", 
          StyleBox[
           FractionBox["1", 
            SubscriptBox["p", "2"]],
           FontSize->18]}], ")"}]}], "..."}], 
      RowBox[{"(", 
       RowBox[{"1", "-", 
        StyleBox[
         FractionBox["1", 
          SubscriptBox["p", "k"]],
         FontSize->18]}], ")"}]}]}],
    FontWeight->"Bold",
    FontColor->GrayLevel[0],
    Background->RGBColor[1, 1, 0.85]], TraditionalForm]]],
 " where ",
 Cell[BoxData[
  FormBox[
   SubscriptBox["p", "1"], TraditionalForm]]],
 ",...",
 Cell[BoxData[
  FormBox[
   SubscriptBox["p", "k"], TraditionalForm]]],
 " are all the prime divisors of n. The following steps should be useful:"
}], "Text",
 CellChangeTimes->{{3.6190083437795057`*^9, 3.619008619778887*^9}, {
   3.6190086997717037`*^9, 3.619008742318366*^9}, {3.61900877337542*^9, 
   3.619008846690468*^9}, {3.619063502179244*^9, 3.619063504155314*^9}, {
   3.619064140835752*^9, 3.619064155080373*^9}, {3.6194770073674107`*^9, 
   3.6194770491064157`*^9}, {3.620075409161674*^9, 3.620075433432282*^9}, {
   3.620075524069899*^9, 3.620075731127187*^9}, {3.620075775367186*^9, 
   3.6200758388256407`*^9}, {3.620075869795953*^9, 3.620076143652358*^9}, {
   3.620076194766493*^9, 3.620076199750688*^9}, {3.620184195501205*^9, 
   3.6201842312101793`*^9}, {3.620184266043998*^9, 3.620184324595572*^9}, {
   3.620184405840395*^9, 3.620184408351913*^9}, 3.620184440649316*^9, {
   3.620184824715065*^9, 3.620184871272209*^9}, {3.620197754934945*^9, 
   3.620197830056409*^9}, {3.622359325175309*^9, 3.622359432517733*^9}, {
   3.62235955393786*^9, 3.622359554581221*^9}, {3.622371481972286*^9, 
   3.622371509950182*^9}, {3.622371543295084*^9, 3.622371551638085*^9}, {
   3.6224072157134237`*^9, 3.622407247968191*^9}, {3.622998078870495*^9, 
   3.622998121459565*^9}, 3.6230007636654882`*^9, {3.70178725968439*^9, 
   3.701787357029542*^9}, {3.701794286291572*^9, 3.701794298708558*^9}, {
   3.7017945965142803`*^9, 3.701794614514885*^9}},
 TextJustification->1.],

Cell[CellGroupData[{

Cell[TextData[{
 "If ",
 Cell[BoxData[
  FormBox["p", TraditionalForm]]],
 " is a prime number, then ",
 Cell[BoxData[
  FormBox[
   RowBox[{
    StyleBox[
     RowBox[{"\[Phi]", "(", "p", ")"}],
     FontWeight->"Bold"], 
    StyleBox["=",
     FontWeight->"Bold"], 
    RowBox[{
     StyleBox[
      RowBox[{"p", "-", "1"}],
      FontWeight->"Bold"], "."}]}], TraditionalForm]]]
}], "ItemNumbered",
 CellChangeTimes->{{3.623070065841669*^9, 3.623070128210013*^9}, {
   3.623070180157112*^9, 3.623070232904689*^9}, {3.6230704373362923`*^9, 
   3.6230704452470007`*^9}, {3.623071042152134*^9, 3.623071069292366*^9}, {
   3.623071170628931*^9, 3.623071176355859*^9}, {3.623072259750602*^9, 
   3.623072275365745*^9}, {3.623072321378746*^9, 3.623072326666456*^9}, {
   3.6230773844685373`*^9, 3.623077403909594*^9}, {3.623676669801736*^9, 
   3.6236766698044*^9}, 3.701794284064436*^9, {3.701794516355207*^9, 
   3.7017945761751957`*^9}},
 TextJustification->1.],

Cell[TextData[{
 "If ",
 Cell[BoxData[
  FormBox["p", TraditionalForm]]],
 " is a prime number and k is a positive integer, then ",
 Cell[BoxData[
  FormBox[
   StyleBox[
    RowBox[{
     RowBox[{"\[Phi]", "(", 
      SuperscriptBox["p", "k"], ")"}], "=", 
     RowBox[{
      SuperscriptBox["p", "k"], "-", 
      SuperscriptBox["p", 
       RowBox[{"k", "-", "1"}]]}]}],
    FontWeight->"Bold"], TraditionalForm]]],
 "."
}], "ItemNumbered",
 CellChangeTimes->{{3.623070065841669*^9, 3.623070128210013*^9}, {
   3.623070180157112*^9, 3.623070232904689*^9}, {3.6230704373362923`*^9, 
   3.6230704452470007`*^9}, {3.623071042152134*^9, 3.623071069292366*^9}, {
   3.623071170628931*^9, 3.623071176355859*^9}, {3.623072259750602*^9, 
   3.623072275365745*^9}, {3.623072321378746*^9, 3.623072326666456*^9}, {
   3.6230773844685373`*^9, 3.623077499395648*^9}, 3.6230776220323687`*^9, {
   3.6230892349971037`*^9, 3.623089235000449*^9}, {3.623106591441285*^9, 
   3.6231066462479687`*^9}, {3.6236026478069353`*^9, 3.623602647810088*^9}, 
   3.701794622866701*^9, {3.701794779328494*^9, 3.701794975074143*^9}},
 TextJustification->1.],

Cell[TextData[{
 "If ",
 Cell[BoxData[
  FormBox["m", TraditionalForm]]],
 " and If ",
 Cell[BoxData[
  FormBox["n", TraditionalForm]]],
 " are relatively prime to each other, then ",
 StyleBox["\[Phi](mn) = \[Phi](m)\[Phi](n)",
  FontWeight->"Bold"],
 "."
}], "ItemNumbered",
 CellChangeTimes->{{3.623070065841669*^9, 3.623070128210013*^9}, {
   3.623070180157112*^9, 3.623070232904689*^9}, {3.6230704373362923`*^9, 
   3.6230704452470007`*^9}, {3.623071042152134*^9, 3.623071069292366*^9}, {
   3.623071170628931*^9, 3.623071176355859*^9}, {3.623072259750602*^9, 
   3.623072275365745*^9}, {3.623072321378746*^9, 3.623072326666456*^9}, {
   3.6230773844685373`*^9, 3.623077499395648*^9}, 3.6230776220323687`*^9, {
   3.6230892349971037`*^9, 3.623089235000449*^9}, {3.623106591441285*^9, 
   3.6231066462479687`*^9}, {3.6236026478069353`*^9, 3.623602647810088*^9}, 
   3.701794622866701*^9, {3.701794779328494*^9, 3.701794870158691*^9}, {
   3.7017949805102158`*^9, 3.701794983666354*^9}, {3.701795480368202*^9, 
   3.701795553280858*^9}, {3.7018152586835546`*^9, 3.701815259738329*^9}},
 TextJustification->1.],

Cell[TextData[{
 "Use the previous steps to prove the general formula for ",
 StyleBox["\[Phi](n)",
  FontWeight->"Bold"],
 "."
}], "ItemNumbered",
 CellChangeTimes->{{3.623070065841669*^9, 3.623070128210013*^9}, {
   3.623070180157112*^9, 3.623070232904689*^9}, {3.6230704373362923`*^9, 
   3.6230704452470007`*^9}, {3.623071042152134*^9, 3.623071069292366*^9}, {
   3.623071170628931*^9, 3.623071176355859*^9}, {3.623072259750602*^9, 
   3.623072275365745*^9}, {3.623072321378746*^9, 3.623072326666456*^9}, {
   3.6230773844685373`*^9, 3.623077499395648*^9}, 3.6230776220323687`*^9, {
   3.6230892349971037`*^9, 3.623089235000449*^9}, {3.623106591441285*^9, 
   3.6231066462479687`*^9}, {3.6236026478069353`*^9, 3.623602647810088*^9}, 
   3.701794622866701*^9, {3.701794779328494*^9, 3.701794870158691*^9}, {
   3.7017949805102158`*^9, 3.701794983666354*^9}, {3.701795480368202*^9, 
   3.7017955788184*^9}, {3.701795931005493*^9, 3.701795931005629*^9}},
 TextJustification->1.],

Cell[TextData[{
 "The plot below shows the first 150 values of the function ",
 StyleBox["\[Phi]",
  FontWeight->"Bold"],
 ". Can you use the graph (and the previous steps) to identify the numbers n \
where the function attains a \[OpenCurlyDoubleQuote]local maximum\
\[CloseCurlyDoubleQuote]? Use your observations to prove that ",
 Cell[BoxData[
  FormBox[
   RowBox[{
    StyleBox[" ",
     FontSlant->"Italic"], 
    RowBox[{
     RowBox[{
      StyleBox[
       UnderscriptBox[
        StyleBox["limsup",
         FontSlant->"Italic"], 
        RowBox[{"n", "\[RightArrow]", "\[Infinity]"}]],
       FontSlant->"Italic"], 
      StyleBox[
       FractionBox[
        RowBox[{"\[Phi]", "(", "n", ")"}], "n"],
       FontSize->18]}], "=", "1"}]}], TraditionalForm]],
  FormatType->"TraditionalForm",
  FontWeight->"Bold"],
 "."
}], "ItemNumbered",
 CellChangeTimes->{{3.623070065841669*^9, 3.623070128210013*^9}, {
   3.623070180157112*^9, 3.623070232904689*^9}, {3.6230704373362923`*^9, 
   3.6230704452470007`*^9}, {3.623071042152134*^9, 3.623071069292366*^9}, {
   3.623071170628931*^9, 3.623071176355859*^9}, {3.623072259750602*^9, 
   3.623072275365745*^9}, {3.623072321378746*^9, 3.623072326666456*^9}, {
   3.6230773844685373`*^9, 3.623077499395648*^9}, 3.6230776220323687`*^9, {
   3.6230892349971037`*^9, 3.623089235000449*^9}, {3.623106591441285*^9, 
   3.6231066462479687`*^9}, {3.6236026478069353`*^9, 3.623602647810088*^9}, 
   3.701794622866701*^9, {3.701794779328494*^9, 3.701794870158691*^9}, {
   3.7017949805102158`*^9, 3.701794983666354*^9}, {3.701795480368202*^9, 
   3.7017955788184*^9}, {3.701795932941437*^9, 3.701795940581843*^9}, {
   3.701814382182683*^9, 3.7018144937851877`*^9}, {3.701814937666113*^9, 
   3.701815046380274*^9}, {3.701815300476131*^9, 3.701815302515711*^9}, {
   3.701815432961296*^9, 3.701815463369277*^9}, {3.7018156918818207`*^9, 
   3.701815727406921*^9}},
 TextJustification->1.]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"DiscretePlot", "[", 
  RowBox[{
   RowBox[{"EulerPhi", "[", "k", "]"}], ",", 
   RowBox[{"{", 
    RowBox[{"k", ",", "150"}], "}"}]}], "]"}]], "Input",
 CellChangeTimes->{{3.701795865051223*^9, 3.701795882809925*^9}, {
  3.701814319309847*^9, 3.7018143243159513`*^9}, {3.7018143543584557`*^9, 
  3.70181435971686*^9}, {3.701814390574153*^9, 3.701814398318096*^9}, {
  3.701816113287406*^9, 3.7018161375916452`*^9}},
 Background->GrayLevel[0.85]],

Cell[BoxData[
 GraphicsBox[{
   {RGBColor[0.368417, 0.506779, 0.709798], PointSize[0.0038500000000000006`],
     AbsoluteThickness[1.6], {
     {RGBColor[0.368417, 0.506779, 0.709798], PointSize[
      0.0038500000000000006`], AbsoluteThickness[1.6], Opacity[0.2], 
      LineBox[{},
       VertexColors->None]}, 
     {RGBColor[0.368417, 0.506779, 0.709798], PointSize[
      0.0038500000000000006`], AbsoluteThickness[1.6], Opacity[0.2], 
      LineBox[{{{1., 1.}, {1., 0}}, {{2., 1.}, {2., 0}}, {{3., 2.}, {
         3., 0}}, {{4., 2.}, {4., 0}}, {{5., 4.}, {5., 0}}, {{6., 2.}, {
         6., 0}}, {{7., 6.}, {7., 0}}, {{8., 4.}, {8., 0}}, {{9., 6.}, {
         9., 0}}, {{10., 4.}, {10., 0}}, {{11., 10.}, {11., 0}}, {{12., 4.}, {
         12., 0}}, {{13., 12.}, {13., 0}}, {{14., 6.}, {14., 0}}, {{15., 
         8.}, {15., 0}}, {{16., 8.}, {16., 0}}, {{17., 16.}, {17., 0}}, {{18.,
          6.}, {18., 0}}, {{19., 18.}, {19., 0}}, {{20., 8.}, {20., 0}}, {{
         21., 12.}, {21., 0}}, {{22., 10.}, {22., 0}}, {{23., 22.}, {
         23., 0}}, {{24., 8.}, {24., 0}}, {{25., 20.}, {25., 0}}, {{26., 
         12.}, {26., 0}}, {{27., 18.}, {27., 0}}, {{28., 12.}, {28., 0}}, {{
         29., 28.}, {29., 0}}, {{30., 8.}, {30., 0}}, {{31., 30.}, {
         31., 0}}, {{32., 16.}, {32., 0}}, {{33., 20.}, {33., 0}}, {{34., 
         16.}, {34., 0}}, {{35., 24.}, {35., 0}}, {{36., 12.}, {36., 0}}, {{
         37., 36.}, {37., 0}}, {{38., 18.}, {38., 0}}, {{39., 24.}, {
         39., 0}}, {{40., 16.}, {40., 0}}, {{41., 40.}, {41., 0}}, {{42., 
         12.}, {42., 0}}, {{43., 42.}, {43., 0}}, {{44., 20.}, {44., 0}}, {{
         45., 24.}, {45., 0}}, {{46., 22.}, {46., 0}}, {{47., 46.}, {
         47., 0}}, {{48., 16.}, {48., 0}}, {{49., 42.}, {49., 0}}, {{50., 
         20.}, {50., 0}}, {{51., 32.}, {51., 0}}, {{52., 24.}, {52., 0}}, {{
         53., 52.}, {53., 0}}, {{54., 18.}, {54., 0}}, {{55., 40.}, {
         55., 0}}, {{56., 24.}, {56., 0}}, {{57., 36.}, {57., 0}}, {{58., 
         28.}, {58., 0}}, {{59., 58.}, {59., 0}}, {{60., 16.}, {60., 0}}, {{
         61., 60.}, {61., 0}}, {{62., 30.}, {62., 0}}, {{63., 36.}, {
         63., 0}}, {{64., 32.}, {64., 0}}, {{65., 48.}, {65., 0}}, {{66., 
         20.}, {66., 0}}, {{67., 66.}, {67., 0}}, {{68., 32.}, {68., 0}}, {{
         69., 44.}, {69., 0}}, {{70., 24.}, {70., 0}}, {{71., 70.}, {
         71., 0}}, {{72., 24.}, {72., 0}}, {{73., 72.}, {73., 0}}, {{74., 
         36.}, {74., 0}}, {{75., 40.}, {75., 0}}, {{76., 36.}, {76., 0}}, {{
         77., 60.}, {77., 0}}, {{78., 24.}, {78., 0}}, {{79., 78.}, {
         79., 0}}, {{80., 32.}, {80., 0}}, {{81., 54.}, {81., 0}}, {{82., 
         40.}, {82., 0}}, {{83., 82.}, {83., 0}}, {{84., 24.}, {84., 0}}, {{
         85., 64.}, {85., 0}}, {{86., 42.}, {86., 0}}, {{87., 56.}, {
         87., 0}}, {{88., 40.}, {88., 0}}, {{89., 88.}, {89., 0}}, {{90., 
         24.}, {90., 0}}, {{91., 72.}, {91., 0}}, {{92., 44.}, {92., 0}}, {{
         93., 60.}, {93., 0}}, {{94., 46.}, {94., 0}}, {{95., 72.}, {
         95., 0}}, {{96., 32.}, {96., 0}}, {{97., 96.}, {97., 0}}, {{98., 
         42.}, {98., 0}}, {{99., 60.}, {99., 0}}, {{100., 40.}, {100., 0}}, {{
         101., 100.}, {101., 0}}, {{102., 32.}, {102., 0}}, {{103., 102.}, {
         103., 0}}, {{104., 48.}, {104., 0}}, {{105., 48.}, {105., 0}}, {{
         106., 52.}, {106., 0}}, {{107., 106.}, {107., 0}}, {{108., 36.}, {
         108., 0}}, {{109., 108.}, {109., 0}}, {{110., 40.}, {110., 0}}, {{
         111., 72.}, {111., 0}}, {{112., 48.}, {112., 0}}, {{113., 112.}, {
         113., 0}}, {{114., 36.}, {114., 0}}, {{115., 88.}, {115., 0}}, {{
         116., 56.}, {116., 0}}, {{117., 72.}, {117., 0}}, {{118., 58.}, {
         118., 0}}, {{119., 96.}, {119., 0}}, {{120., 32.}, {120., 0}}, {{
         121., 110.}, {121., 0}}, {{122., 60.}, {122., 0}}, {{123., 80.}, {
         123., 0}}, {{124., 60.}, {124., 0}}, {{125., 100.}, {125., 0}}, {{
         126., 36.}, {126., 0}}, {{127., 126.}, {127., 0}}, {{128., 64.}, {
         128., 0}}, {{129., 84.}, {129., 0}}, {{130., 48.}, {130., 0}}, {{
         131., 130.}, {131., 0}}, {{132., 40.}, {132., 0}}, {{133., 108.}, {
         133., 0}}, {{134., 66.}, {134., 0}}, {{135., 72.}, {135., 0}}, {{
         136., 64.}, {136., 0}}, {{137., 136.}, {137., 0}}, {{138., 44.}, {
         138., 0}}, {{139., 138.}, {139., 0}}, {{140., 48.}, {140., 0}}, {{
         141., 92.}, {141., 0}}, {{142., 70.}, {142., 0}}, {{143., 120.}, {
         143., 0}}, {{144., 48.}, {144., 0}}, {{145., 112.}, {145., 0}}, {{
         146., 72.}, {146., 0}}, {{147., 84.}, {147., 0}}, {{148., 72.}, {
         148., 0}}, {{149., 148.}, {149., 0}}, {{150., 40.}, {150., 0}}},
       VertexColors->None]}}}, 
   {RGBColor[0.368417, 0.506779, 0.709798], PointSize[0.0038500000000000006`],
     AbsoluteThickness[1.6], {}, PointBox[CompressedData["
1:eJxdlM1Ok1EQhhtXLlm4YOGiGGIIMUYRQX6UYy1UUEppC7aA9KOJa29hrsJ1
L+VcCpfgJaDhfRbzkpDJ807n90y7Mv89/PWk1Wr9+ff/3z7+/T3ItlUyPy1Z
XzJ+Zvqy+Z+b3rbPvzD/qvlfmr5m/nXTX1m+11b3jfFb0zcs/p3pmxb/3upv
Wb/bpn+w+B3Lu2v59qz+vvk/mv7J8h+YXmQ1b8DU/2x+mL47uX50TP+S+w2Y
+K7l75p+aPkPTT/K/QZM/p6s9h09079afZj8x5YfZk8nuV6cmP5Nlvlh5vtu
8XBH9lRW7xmnpvet/77pZ7J674DJP8jzFFh7CFjz14Hp5xYP6x0C1nz13PRh
9pdh1gNWvxVmf6PsL7DmD5j6I9PH1j+sdwpY9erY9AvrH2ZPsO6pwrzzZc5f
LrMeMP3D7OGHrPZdYOaHde8VJn4iy/yTrAdM/zD3NbX+p1kPWPmr61eyurdi
HLC+T/XK9GvZjuKvsx4w7wcz/43Vv8l6wMpfYd7hp6zes8DcL6zva4XZ460s
+7/NfQd+7bvC3N8s+wvMnmH6n5neyOpe27DutMDaT9NkPfBrvwtY/Vc+p/z3
+Nn/ndW/y3qBdd+N6YFf/S1g3Xnlc/q9ucfPHuc5vg3rnQusfhtY+wnzL+ZZ
r/i75QHxK9FJ
     "]], {}}},
  AspectRatio->NCache[GoldenRatio^(-1), 0.6180339887498948],
  Axes->True,
  AxesOrigin->{1, 0},
  FrameTicks->{{Automatic, Automatic}, {Automatic, Automatic}},
  GridLinesStyle->Directive[
    GrayLevel[0.5, 0.4]],
  ImageSize->{498.56640625, Automatic},
  Method->{
   "MessagesHead" -> DiscretePlot, "AxisPadding" -> Scaled[0.02], 
    "DefaultBoundaryStyle" -> Automatic, "DefaultMeshStyle" -> 
    AbsolutePointSize[6], "DefaultPlotStyle" -> {
      Directive[
       RGBColor[0.368417, 0.506779, 0.709798], 
       AbsoluteThickness[1.6]], 
      Directive[
       RGBColor[0.880722, 0.611041, 0.142051], 
       AbsoluteThickness[1.6]], 
      Directive[
       RGBColor[0.560181, 0.691569, 0.194885], 
       AbsoluteThickness[1.6]], 
      Directive[
       RGBColor[0.922526, 0.385626, 0.209179], 
       AbsoluteThickness[1.6]], 
      Directive[
       RGBColor[0.528488, 0.470624, 0.701351], 
       AbsoluteThickness[1.6]], 
      Directive[
       RGBColor[0.772079, 0.431554, 0.102387], 
       AbsoluteThickness[1.6]], 
      Directive[
       RGBColor[0.363898, 0.618501, 0.782349], 
       AbsoluteThickness[1.6]], 
      Directive[
       RGBColor[1, 0.75, 0], 
       AbsoluteThickness[1.6]], 
      Directive[
       RGBColor[0.647624, 0.37816, 0.614037], 
       AbsoluteThickness[1.6]], 
      Directive[
       RGBColor[0.571589, 0.586483, 0.], 
       AbsoluteThickness[1.6]], 
      Directive[
       RGBColor[0.915, 0.3325, 0.2125], 
       AbsoluteThickness[1.6]], 
      Directive[
       RGBColor[0.40082222609352647`, 0.5220066643438841, 0.85], 
       AbsoluteThickness[1.6]], 
      Directive[
       RGBColor[0.9728288904374106, 0.621644452187053, 0.07336199581899142], 
       AbsoluteThickness[1.6]], 
      Directive[
       RGBColor[0.736782672705901, 0.358, 0.5030266573755369], 
       AbsoluteThickness[1.6]], 
      Directive[
       RGBColor[0.28026441037696703`, 0.715, 0.4292089322474965], 
       AbsoluteThickness[1.6]]}, "DomainPadding" -> Scaled[0.02], 
    "PointSizeFunction" -> "SmallPointSize", "RangePadding" -> Scaled[0.05]},
  PlotRange->{{1, 150}, {0, 148.}},
  PlotRangePadding->{{
     Scaled[0.02], 
     Scaled[0.02]}, {
     Scaled[0.02], 
     Scaled[0.02]}},
  Ticks->{Automatic, Automatic}]], "Output",
 CellChangeTimes->{{3.701795866582367*^9, 3.701795883550578*^9}, {
  3.7018143203817167`*^9, 3.701814360513982*^9}, {3.701814392994515*^9, 
  3.7018143987733192`*^9}, {3.701816114812676*^9, 3.701816139759089*^9}}]
}, Open  ]],

Cell[TextData[{
 "One should not understand from part 5 that ",
 Cell[BoxData[
  FormBox[
   RowBox[{
    RowBox[{
     StyleBox[
      UnderscriptBox[
       StyleBox["lim",
        FontSlant->"Italic"], 
       RowBox[{"n", "\[RightArrow]", "\[Infinity]"}]],
      FontSlant->"Italic"], 
     StyleBox[
      FractionBox[
       RowBox[{"\[Phi]", "(", "n", ")"}], "n"],
      FontSize->18]}], "=", "1"}], TraditionalForm]],
  FormatType->"TraditionalForm",
  FontWeight->"Bold"],
 ". In fact Schinzel and Sierpi\:0144ski showed that the set ",
 StyleBox["S=",
  FontWeight->"Bold"],
 Cell[BoxData[
  FormBox[
   RowBox[{
    StyleBox["{",
     FontSlant->"Italic"], 
    RowBox[{
     StyleBox[
      FractionBox[
       RowBox[{"\[Phi]", "(", "n", ")"}], "n"],
      FontSize->18], 
     StyleBox[",",
      FontSize->18], 
     StyleBox[
      RowBox[{"n", "=", "1"}],
      FontSize->16], 
     StyleBox[",",
      FontSize->16], 
     StyleBox["2",
      FontSize->16], 
     StyleBox[",",
      FontSize->16], 
     StyleBox["3",
      FontSize->16], 
     StyleBox[",",
      FontSize->16], 
     StyleBox["...",
      FontSize->16]}], "}"}], TraditionalForm]],
  FontWeight->"Bold"],
 " is dense in the interval ",
 StyleBox["[0,1]",
  FontWeight->"Bold"],
 ". In particular, ",
 Cell[BoxData[
  FormBox[
   RowBox[{
    RowBox[{
     StyleBox[
      UnderscriptBox[
       StyleBox["liminf",
        FontSlant->"Italic"], 
       RowBox[{"n", "\[RightArrow]", "\[Infinity]"}]],
      FontSlant->"Italic"], 
     StyleBox[
      FractionBox[
       RowBox[{"\[Phi]", "(", "n", ")"}], "n"],
      FontSize->18]}], "=", "0"}], TraditionalForm]],
  FontWeight->"Bold"],
 ". Give evidence of this density result by plotting the set S for the first \
100,1000 and 10000 positive integer numbers. Choose the appropriate plotting \
functions!"
}], "ItemNumbered",
 CellChangeTimes->{{3.623070065841669*^9, 3.623070128210013*^9}, {
   3.623070180157112*^9, 3.623070232904689*^9}, {3.6230704373362923`*^9, 
   3.6230704452470007`*^9}, {3.623071042152134*^9, 3.623071069292366*^9}, {
   3.623071170628931*^9, 3.623071176355859*^9}, {3.623072259750602*^9, 
   3.623072275365745*^9}, {3.623072321378746*^9, 3.623072326666456*^9}, {
   3.6230773844685373`*^9, 3.623077499395648*^9}, 3.6230776220323687`*^9, {
   3.6230892349971037`*^9, 3.623089235000449*^9}, {3.623106591441285*^9, 
   3.6231066462479687`*^9}, {3.6236026478069353`*^9, 3.623602647810088*^9}, 
   3.701794622866701*^9, {3.701794779328494*^9, 3.701794870158691*^9}, {
   3.7017949805102158`*^9, 3.701794983666354*^9}, {3.701795480368202*^9, 
   3.7017955788184*^9}, {3.701795932941437*^9, 3.701795940581843*^9}, {
   3.701814382182683*^9, 3.7018144937851877`*^9}, {3.701814937666113*^9, 
   3.701815046380274*^9}, {3.701815300476131*^9, 3.701815302515711*^9}, {
   3.701815432961296*^9, 3.701815463369277*^9}, {3.701815648283709*^9, 
   3.701815666431834*^9}, {3.701815739763299*^9, 3.701815947209529*^9}, {
   3.701815999653751*^9, 3.7018160019551277`*^9}, {3.7018161518882637`*^9, 
   3.7018162687483597`*^9}, {3.701816489851501*^9, 3.7018164944438353`*^9}, {
   3.701816590744129*^9, 3.701816627024591*^9}, 3.701822056192649*^9},
 TextJustification->1.],

Cell[BoxData[""], "Input",
 CellChangeTimes->{{3.701816949136945*^9, 3.701816968418715*^9}}]
}, Open  ]],

Cell[CellGroupData[{

Cell[TextData[StyleBox["Problem 4.2 ", "Subsection"]], "Section",
 CellChangeTimes->{{3.6188834470493517`*^9, 3.618883458254191*^9}, {
   3.6188841737965927`*^9, 3.618884177712782*^9}, {3.6188846295181627`*^9, 
   3.6188846297983932`*^9}, {3.619056965231044*^9, 3.619056965742797*^9}, {
   3.620184812387269*^9, 3.620184812898695*^9}, {3.620185327776074*^9, 
   3.620185327888328*^9}, {3.622348234232251*^9, 3.622348237600342*^9}, {
   3.623068761984556*^9, 3.6230687632311697`*^9}, {3.701787196531636*^9, 
   3.701787197051684*^9}, 3.7018186386982613`*^9, {3.7018209855655203`*^9, 
   3.701820985699428*^9}}],

Cell[TextData[{
 "Consider an affine cipher ",
 Cell[BoxData[
  FormBox[
   RowBox[{
    RowBox[{
     SubscriptBox["E", 
      RowBox[{"a", ",", "b"}]], "(", "x", ")"}], "=", 
    RowBox[{"ax", "+", 
     RowBox[{"b", " ", 
      RowBox[{"(", 
       RowBox[{"mod", " ", "26"}], ")"}]}]}]}], TraditionalForm]],
  FontWeight->"Bold"],
 ", where a and b are integer numbers between 0 and 25, and a and 26 are \
relatively prime."
}], "Text",
 CellChangeTimes->{{3.6190083437795057`*^9, 3.619008619778887*^9}, {
   3.6190086997717037`*^9, 3.619008742318366*^9}, {3.61900877337542*^9, 
   3.619008846690468*^9}, {3.619063502179244*^9, 3.619063504155314*^9}, {
   3.619064140835752*^9, 3.619064155080373*^9}, {3.6194770073674107`*^9, 
   3.6194770491064157`*^9}, {3.620075409161674*^9, 3.620075433432282*^9}, {
   3.620075524069899*^9, 3.620075731127187*^9}, {3.620075775367186*^9, 
   3.6200758388256407`*^9}, {3.620075869795953*^9, 3.620076143652358*^9}, {
   3.620076194766493*^9, 3.620076199750688*^9}, {3.620184195501205*^9, 
   3.6201842312101793`*^9}, {3.620184266043998*^9, 3.620184324595572*^9}, {
   3.620184405840395*^9, 3.620184408351913*^9}, 3.620184440649316*^9, {
   3.620184824715065*^9, 3.620184871272209*^9}, {3.620197754934945*^9, 
   3.620197830056409*^9}, {3.622359325175309*^9, 3.622359432517733*^9}, {
   3.62235955393786*^9, 3.622359554581221*^9}, {3.622371481972286*^9, 
   3.622371509950182*^9}, {3.622371543295084*^9, 3.622371551638085*^9}, {
   3.6224072157134237`*^9, 3.622407247968191*^9}, {3.622998078870495*^9, 
   3.622998121459565*^9}, 3.6230007636654882`*^9, {3.70178725968439*^9, 
   3.701787357029542*^9}, {3.701794286291572*^9, 3.701794298708558*^9}, {
   3.7017945965142803`*^9, 3.701794614514885*^9}, {3.7018186618835783`*^9, 
   3.7018187617571707`*^9}, {3.701822049216069*^9, 3.701822049565206*^9}},
 TextJustification->1.],

Cell[CellGroupData[{

Cell["a) Encoding/Decoding", "Subsubsection",
 CellChangeTimes->{{3.624208063172361*^9, 3.624208090268035*^9}, {
  3.656319060033389*^9, 3.6563190632587147`*^9}, {3.6563194536706877`*^9, 
  3.656319461934849*^9}, {3.6563250726923933`*^9, 3.656325073580098*^9}, {
  3.70181879159128*^9, 3.701818819030593*^9}}],

Cell["\<\
Assume that the key is {a,b}={3,7}. Encode the text \
\[OpenCurlyDoubleQuote]Summer is coming\[CloseCurlyDoubleQuote]. Decode the \
following text \
\[OpenCurlyDoubleQuote]\
MCFJCXRTVXGLFJMCTOHJMCXRTVXGLHJJFZURTUMXWMCTNXPGJTVTVFOOXUOBCHSTXUTRXGTAGXITNM\
\[CloseCurlyDoubleQuote] \
\>", "Text",
 CellChangeTimes->{{3.6563194864647903`*^9, 3.656319492686431*^9}, 
   3.70170511787109*^9, {3.7018188345285883`*^9, 3.701818892170233*^9}, {
   3.7018191442501574`*^9, 3.7018191952107077`*^9}, {3.7018201860941267`*^9, 
   3.701820197482511*^9}}]
}, Open  ]],

Cell[CellGroupData[{

Cell["\<\
b) Cryptanalysis by exhaustive key search, or brute-force approach (try all \
possible keys):\
\>", "Subsubsection",
 CellChangeTimes->{{3.624208063172361*^9, 3.624208090268035*^9}, {
   3.656319060033389*^9, 3.6563190632587147`*^9}, {3.6563194536706877`*^9, 
   3.656319461934849*^9}, {3.6563250726923933`*^9, 3.656325073580098*^9}, {
   3.70181922708057*^9, 3.701819267492937*^9}, {3.701820128546487*^9, 
   3.701820128975873*^9}, 3.701820230467593*^9}],

Cell["\<\
What is the dimension of the key space of an Affine Cipher? The following \
text \[OpenCurlyDoubleQuote]\
APQPKHPMMFVYOSDQLDDQACYDVSKWZMZDMZKHZQKFYPJMRPMZSZKKZMLVQKWZDSOWDCZK\
\[CloseCurlyDoubleQuote] has been encoded using an Affine Cipher. Decode the \
text.\
\>", "Text",
 CellChangeTimes->{{3.6563194864647903`*^9, 3.656319492686431*^9}, 
   3.70170511787109*^9, 3.7018200588839197`*^9, {3.701820095240428*^9, 
   3.70182010601544*^9}, {3.701820182662594*^9, 3.7018202003704443`*^9}, {
   3.7018222762123833`*^9, 3.701822297365137*^9}}],

Cell[TextData[{
 StyleBox["Hint: ",
  FontWeight->"Bold"],
 "After you generate all possible decodings, the Wolfram function ",
 StyleBox["LanguageIdentify[...]",
  FontWeight->"Bold"],
 " might help you narrow down the search."
}], "Text",
 CellChangeTimes->{{3.6242113834663057`*^9, 3.624211433127977*^9}, {
   3.656325805915979*^9, 3.6563258064763308`*^9}, {3.7018202942786827`*^9, 
   3.7018203108781157`*^9}, 3.701822270159059*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell["c) Cryptanalysis by the method of a known ciphertext:", "Subsubsection",
 CellChangeTimes->{{3.624208063172361*^9, 3.624208090268035*^9}, {
   3.656325076253151*^9, 3.6563250772056293`*^9}, {3.701819250224174*^9, 
   3.701819271132989*^9}, {3.701820130841254*^9, 3.701820131600258*^9}, 
   3.7018202323955603`*^9}],

Cell["\<\
Suppose that an affine cipher E(x) = ax+b (mod 26) enciphers \
\[OpenCurlyDoubleQuote]J\[CloseCurlyDoubleQuote] as \[OpenCurlyDoubleQuote]S\
\[CloseCurlyDoubleQuote] and \[OpenCurlyDoubleQuote]M\[CloseCurlyDoubleQuote] \
as \[OpenCurlyDoubleQuote]B\[CloseCurlyDoubleQuote] and \
\[OpenCurlyDoubleQuote]W\[CloseCurlyDoubleQuote] as \[OpenCurlyDoubleQuote]F\
\[CloseCurlyDoubleQuote]. Find the key. Do you need to use all three known \
ciphertexts to break the cipher? Use the key to decode the ciphertext  
\[OpenCurlyDoubleQuote]PGLHZXREQDRAWMPTPWBDRETWMRWLHZMRCDADXHADAWMDWDIW\
\[CloseCurlyDoubleQuote], 
which has been encoded using the same cipher.  \
\>", "Text",
 CellChangeTimes->{{3.6242082478670588`*^9, 3.624208341271936*^9}, {
   3.624208493532267*^9, 3.6242085043715477`*^9}, {3.624210781324059*^9, 
   3.624210791403756*^9}, {3.624211479746768*^9, 3.6242114804967012`*^9}, 
   3.701820327543799*^9, {3.701820779261959*^9, 3.701820872199667*^9}, {
   3.7018209022087317`*^9, 3.7018209594827547`*^9}},
 TextJustification->1.],

Cell[TextData[{
 StyleBox["Hint: ",
  FontWeight->"Bold"],
 "Solve a system of linear equations modulo 26."
}], "Text",
 CellChangeTimes->{{3.6242113834663057`*^9, 3.624211433127977*^9}, {
  3.656325805915979*^9, 3.6563258064763308`*^9}, {3.7018208782718143`*^9, 
  3.701820882791883*^9}}]
}, Open  ]],

Cell[CellGroupData[{

Cell["d) Cryptanalysis by frequency analysis:", "Subsubsection",
 CellChangeTimes->{{3.624208081883882*^9, 3.6242080879403677`*^9}, {
   3.624208930116665*^9, 3.6242089342847433`*^9}, {3.656325079334611*^9, 
   3.656325080294981*^9}, {3.656325114234623*^9, 3.656325124268654*^9}, {
   3.7018192419197893`*^9, 3.7018192741811543`*^9}, {3.7018201355694447`*^9, 
   3.701820136121194*^9}, 3.701820234547434*^9}],

Cell["\<\
Suppose that you have intercepted the following ciphertext 
\[OpenCurlyDoubleQuote]\
ZVDFVQZLMWDQFVSSLIDZLMWDQFMDQTJUVULXIZLMWDQFFLTMEDTXIXVEMWVKDULZFJKFULUJULXIZL\
MWDQFVQDIXUFDZJQDJIELPDZVDFVQFZLMWDQVMDQTJUVULXIZLMWDQOXDFIXUWVYDUWDOQVNKVZPXS\
VFTVEEPDRFMVZDWVYLIHVEVQHDPDRFMVZDOXDFIXUTDVIUWVUUWDFRFUDTLFFDZJQDXIUWDZXIUQVQ\
RKRFLTMERZXJIULIHUWDEDUUDQSQDBJDIZLDFLIUWDZLMWDQUDCUVIOZXTMVQLIHUWDFDNLUWUWDED\
UUDQSQDBJDIZLDFXSUWDDIHELFWVEMWVKDUXIDYDQRBJLZPERSLIOFUWDLTVHDFJIODQUWDMDQTJUV\
ULXIMXSUWDTXFUSQDBJDIUEDUUDQFLIUWDMEVLIUDCU\[CloseCurlyDoubleQuote].
You know that it has been encoded using an affine cipher, but you don' t know \
the key. Use frequency analysis to break the cipher. \
\>", "Text",
 CellChangeTimes->{{3.624209715352704*^9, 3.624209789136374*^9}, {
   3.6242128806216297`*^9, 3.624212893583449*^9}, 3.701819283637951*^9, {
   3.701819367241418*^9, 3.701819373386078*^9}, 3.701820208483053*^9}],

Cell[TextData[{
 StyleBox["Hint: ",
  FontWeight->"Bold"],
 "The frequencies of the letters in the English alphabet are given below:"
}], "Text",
 CellChangeTimes->{{3.6242113834663057`*^9, 3.624211433127977*^9}, {
  3.656325805915979*^9, 3.6563258064763308`*^9}, {3.701820347336411*^9, 
  3.7018203784723997`*^9}}],

Cell[BoxData[{
 RowBox[{
  RowBox[{"T", "=", 
   RowBox[{"{", 
    RowBox[{
     RowBox[{"\"\<A\>\"", "\[Rule]", " ", "0.0804"}], ",", " ", 
     RowBox[{"\"\<B\>\"", "\[Rule]", " ", "0.0154"}], ",", " ", 
     RowBox[{"\"\<C\>\"", "\[Rule]", "0.0306"}], ",", " ", 
     RowBox[{"\"\<D\>\"", "\[Rule]", "0.0399"}], ",", " ", 
     RowBox[{"\"\<E\>\"", "\[Rule]", "0.1251"}], ",", " ", 
     RowBox[{"\"\<F\>\"", "\[Rule]", "0.0230"}], ",", " ", 
     RowBox[{"\"\<G\>\"", "\[Rule]", "0.0196"}], ",", " ", 
     RowBox[{"\"\<H\>\"", "\[Rule]", "0.0549"}], ",", " ", 
     RowBox[{"\"\<I\>\"", "\[Rule]", "0.0726"}], ",", " ", 
     RowBox[{"\"\<J\>\"", "\[Rule]", "0.0016"}], ",", " ", 
     RowBox[{"\"\<K\>\"", "\[Rule]", "0.0067"}], ",", " ", 
     RowBox[{"\"\<L\>\"", "\[Rule]", "0.0414"}], ",", " ", 
     RowBox[{"\"\<M\>\"", "\[Rule]", "0.0253"}], ",", 
     RowBox[{"\"\<N\>\"", "\[Rule]", "0.0709"}], ",", 
     RowBox[{"\"\<O\>\"", "\[Rule]", "0.0760"}], ",", 
     RowBox[{"\"\<P\>\"", "\[Rule]", "0.0200"}], ",", " ", 
     RowBox[{"\"\<Q\>\"", "\[Rule]", "0.0011"}], ",", 
     RowBox[{"\"\<R\>\"", "\[Rule]", "0.0612"}], ",", " ", 
     RowBox[{"\"\<S\>\"", "\[Rule]", "0.0654"}], ",", " ", 
     RowBox[{"\"\<T\>\"", "\[Rule]", "0.0925"}], ",", " ", 
     RowBox[{"\"\<U\>\"", "\[Rule]", "0.0271"}], ",", " ", 
     RowBox[{"\"\<V\>\"", "\[Rule]", "0.0099"}], ",", " ", 
     RowBox[{"\"\<W\>\"", "\[Rule]", "0.0192"}], ",", " ", 
     RowBox[{"\"\<X\>\"", "\[Rule]", "0.0019"}], ",", " ", 
     RowBox[{"\"\<Y\>\"", "\[Rule]", "0.0173"}], ",", " ", 
     RowBox[{"\"\<Z\>\"", "\[Rule]", "0.0009"}]}], "}"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"TA", "=", 
   RowBox[{"Association", "[", "T", "]"}]}], ";"}], "\[IndentingNewLine]", 
 RowBox[{"Sort", "[", "TA", "]"}]}], "Input",
 CellChangeTimes->{{3.624205834253846*^9, 3.6242062567257833`*^9}, {
  3.701817745230565*^9, 3.701817745986498*^9}, {3.701818215597114*^9, 
  3.701818259909519*^9}, {3.7018182913121777`*^9, 3.701818295438904*^9}},
 Background->GrayLevel[0.85]]
}, Open  ]]
}, Open  ]]
},
WindowSize->{808, 556},
WindowMargins->{{Automatic, 88}, {Automatic, 0}},
FrontEndVersion->"11.0 for Mac OS X x86 (32-bit, 64-bit Kernel) (September \
21, 2016)",
StyleDefinitions->"Default.nb"
]
(* End of Notebook Content *)

(* Internal cache information *)
(*CellTagsOutline
CellTagsIndex->{}
*)
(*CellTagsIndex
CellTagsIndex->{}
*)
(*NotebookFileOutline
Notebook[{
Cell[558, 20, 457, 11, 64, "Section"],
Cell[CellGroupData[{
Cell[1040, 35, 526, 7, 41, "Section"],
Cell[1569, 44, 2709, 66, 106, "Text"],
Cell[CellGroupData[{
Cell[4303, 114, 961, 26, 30, "ItemNumbered"],
Cell[5267, 142, 1129, 27, 38, "ItemNumbered"],
Cell[6399, 171, 1112, 23, 30, "ItemNumbered"],
Cell[7514, 196, 979, 17, 30, "ItemNumbered"],
Cell[8496, 215, 1932, 43, 89, "ItemNumbered"]
}, Open  ]],
Cell[CellGroupData[{
Cell[10465, 263, 469, 10, 48, "Input"],
Cell[10937, 275, 8052, 149, 327, "Output"]
}, Open  ]],
Cell[19004, 427, 3217, 90, 120, "ItemNumbered"],
Cell[22224, 519, 92, 1, 32, "Input"]
}, Open  ]],
Cell[CellGroupData[{
Cell[22353, 525, 609, 8, 55, "Section"],
Cell[22965, 535, 1861, 35, 53, "Text"],
Cell[CellGroupData[{
Cell[24851, 574, 309, 4, 35, "Subsubsection"],
Cell[25163, 580, 550, 11, 68, "Text"]
}, Open  ]],
Cell[CellGroupData[{
Cell[25750, 596, 465, 8, 35, "Subsubsection"],
Cell[26218, 606, 550, 10, 68, "Text"],
Cell[26771, 618, 436, 10, 49, "Text"]
}, Open  ]],
Cell[CellGroupData[{
Cell[27244, 633, 320, 4, 35, "Subsubsection"],
Cell[27567, 639, 1045, 17, 106, "Text"],
Cell[28615, 658, 289, 7, 30, "Text"]
}, Open  ]],
Cell[CellGroupData[{
Cell[28941, 670, 408, 5, 35, "Subsubsection"],
Cell[29352, 677, 923, 14, 182, "Text"],
Cell[30278, 693, 315, 7, 30, "Text"],
Cell[30596, 702, 2057, 39, 175, "Input"]
}, Open  ]]
}, Open  ]]
}
]
*)