MAT102 Lecture 18B

• Fermat's Little Theorem
• #tk prove euler totient theorem
  • Define the euler totient theorem
  • $\varphi :{\mathbb{Z}}^{+}\to {\mathbb{Z}}^{+}$
  • $\varphi (m)=|\{k\in {\mathbb{Z}}^{+}P:gcd(k,m)=1\text{ and }1\le k\le m\}|$
  • Counting the number of things $\le m$ which are coprime to $m$
  • That should basically be everything if $p$ is prime except $1$
  • Ex:
    • $\varphi (6)=2$
    • $\varphi (11)=10$ because $p=11$ is prime
    • $\varphi (p)=p-1$
    • $a^{\varphi (m)}\equiv 1(\mathrm{mod}m)$
    • When $m$ is prime, this is Fermat's Little Theorem
      09NumberTheoryIIIExercises_Students.pdf
• 1
  • Solve the equation $6x\equiv 2(\mathrm{mod}8)$
    • $8\mid 6x-2$
    • $3$ is a solution
      • $8\mid 6(3)-2$
      • $8\mid 16$
    • $7$ is a solution
      • $8\mid 6(7)-2$
      • $8\mid 40$
  • Does $6x\equiv 3(\mathrm{mod}8)$ have a solution?
    • $8\mid 6x-3$
    • No, not in $(\mathrm{mod}8)$
• 2
  • Prove that $ax\equiv c(\mathrm{mod}m)$ has a solution $x=x_0⟺$ there exists $y_0\in \mathbb{Z}$ such that $a{x}_0+m{y}_0=c$
  • $⟹$
    • $m\mid ax-c$
    • $mk=ax-c$ for some $k\in \mathbb{Z}$
    • Prove that $y_0\in \mathbb{Z}$ where $a{x}_0+m{y}_0=c$
    • $a{x}_0+m{y}_0=c$
    • This will have solutions if $gcd(a,m)=1$
    • Then $c$ is the multiple on $(x_0,y_0)$
    • $ax-mk=c$
    • $a{x}_0+m{y}_0=ax-mk$
    • If we have a solution $x_0$
    • Then $a{x}_0+m{y}_0=a{x}_0-mk$
    • $m{y}_0=-mk$
    • $y_0=-k$
    • There is a solution
  • $⟸$
    • There's a solution $y_0$
    • $a{x}_0+m{y}_0=c$
    • Solutions when $gcd(a,m)=1$ and $c$ is the multiple of the solutions
    • Prove that there's a solution to $ax\equiv c(\mathrm{mod}m)$
    • $m\mid (ax-c)$
    • $mk=ax-c$
    • $ax-mk=c$
    • $a{x}_0+m{y}_0=c$
    • $a{x}_0+m{y}_0=ax-mk$
    • Since we know that $y_0=-k$
    • Then $a{x}_0+m{y}_0=ax+m(-k)$
    • So clearly $a{x}_0+ax$ so then $x=x_0$
• 3
  • $ax\equiv c(\mathrm{mod}m)⟺gcd(a,m)\mid c$
  • ${}^{†}x\equiv x_0(\mathrm{mod}\frac{m}{d})$
  • ${}^{††}x\equiv x_0+k\frac{m}{d}(\mathrm{mod}m)$ for $k=0,1,\dots ,d-1$
  • a
    • Show that a solution exists $⟺$ $gcd(a,m)\mid c$
    • $x\equiv x_0(\mathrm{mod}\frac{m}{d})$
    • $\frac{m}{d}\mid x-x_0$
    • $\frac{m}{d}k=x-x_0$
    • $mk=d(x-x_0)$
    • $mk=dx-d{x}_0$
    • $dx-mk=d{x}_0$
    • $a{x}_0+m{y}_0=dx-mk$
    • Solutions if $gcd(a,m)=1$ $c$ is the multiple of the solutions.
    • So by part 2), this is true.
  • b
    • Show that general form of solutions to diophantine equations are $†$
    • $x=x_0+n\frac{a}{d}$
    • $y=y_0-n\frac{a}{d}$
    • $ax\equiv c(\mathrm{mod}m)$
    • $\dots$
    • $ax-mk=c$
    • $a{x}_0+m{y}_0=c$
    • $y_0=-k$
    • $y=-k-n\frac{a}{d}$
    • $x=x_0+n\frac{a}{d}$
    • $\dots$
    • $x\equiv x_0(\mathrm{mod}\frac{m}{d})$
    • $\frac{m}{d}\mid x-x_0$
    • $\frac{m}{d}k=x-x_0$
    • $mk=dx-d{x}_0$
    • $dx-mk=d{x}_0$
    • $a{x}_0+m{y}_0=dx-mk$
    • $a(x_0+n\frac{a}{d})+m(-k-n\frac{a}{d})=dx-mk$
    • $a{x}_0+\frac{a^{2}n}{d}-mk-\frac{nam}{d}=dx-mk$
    • $da{x}_0+a^{2}n-mk-nam=d^{2}x-dmk$
    • $da{x}_0+a^{2}n-mk-nam=cd{x}_0$
    • $a(d{x}_0+an)-mk-nam=cd{x}_0$
    • $a(d{x}_0+an)-(dx-d{x}_0)-nam=cd{x}_0$
    • $ad{x}_0+a^{2}n-dx+d{x}_0-nam=cd{x}_0$
    • $a^{2}n-dx+(a+1)d{x}_0-nam=cd{x}_0$
    • $a^{2}n+(a+1)(-mk)-nam=cd{x}_0$
    • $a^{2}n-(a+1)(mk)-nam=cd{x}_0$
• #tk