MAT102 Tutorial W9

• 1
  • Show that $\mathrm{\forall }\in \mathbb{N},6\mid 7^n-1$
  • $P(n)=6{\mid }_7^n-1$
  • Show $P(1)$ is true:
    • $P(1)=6\mid 7^1-1$
    • This is true
  • Does $P(n)⟹P(n+1)$
    • Suppose $P(n)$ is true
    • Does $P(n)⟹P(n+1)$
    • $6\mid 7^n-1⟹7^n-1=6k$ for some $k\in \mathbb{Z}$
      • $7^n=6k+1$
    • $6\mid 7^{n+1}-1$
      • $6\mid 7^{n+1}-1$
      • $6\mid 7\cdot 7^n-1⟹7\cdot (6k+1)-1$
      • $7\cdot (6k+1)-1$
      • $42k+7-1$
      • $42k+6$
      • $6\mid 6(7k+1)$
      • This is true, so via induction, this is true for all $n$
  • Solution:
    • Oneliner:
      • Notice that $\to$
      • $7^n-1\equiv 1^n-1\equiv 1-1\equiv 0(\mathrm{mod}6)$
    • Induction:
      • Base Case:
        • $n=1:7-1=6$
        • $6\mid 6$
      • Induction:
        • Assume that $6\mid 7^k-1$ for some $k\in \mathbb{Z}$
        • Show that $6\mid 7^{k+1}-1$
          • $6\mid 7^k-1$
          • $6\mid 7(7^k-1)$
          • $6\mid 7^{k+1}-7$
          • $7^{k+1}-7=6m$ for some $m\in \mathbb{Z}$
          • $7^{k+1}-7=6m$
          • $7^{k+1}-7=6(m+1)$
          • $6\mid 7^{k+1}-1$
• 2
  • Show that if $a\equiv b(\mathrm{mod}n)$ then $a^k\equiv b^k(\mathrm{mod}n)$
  • This means that $n\mid b^k-a^k$
    • So $b^k-a^k=nc$ for some $c\in \mathbb{Z}$
  • Base Case:
    • $a^1\equiv b^1(\mathrm{mod}n)$
    • $a\equiv b(\mathrm{mod}n)$
    • True
  • Induction Hypothesis:
    • Suppose for $m$ (arbitrary), that $a^m\equiv b^m(\mathrm{mod}n)$
    • This means $b^m-a^m=nc$ for some $c\in \mathbb{Z}$
  • Induction:
    • Let $k=m+1$
    • Show that $a^{m+1}\equiv b^{m+1}(\mathrm{mod}n)$
    • $a\cdot a^m\equiv b\cdot b^m(\mathrm{mod}n)$
    • $b=a+nd$ for some $d\in \mathbb{Z}$
    • $b^m=a^m+nc$
    • $b^{m+1}-a^{m+1}=(a+nd)(a^m+nc)-a\cdot a^m$
    • $b^{m+1}-a^{m+1}=a^{m+1}+nca+nd{a}^m+n^{2}cd-a^{m+1}$
    • $b^{m+1}-a^{m+1}=n(ca+d{a}^m+ncd)$
    • So we have shown that $a^{m+1}\equiv b^{m+1}(\mathrm{mod}n)$, by showing $n\mid b^{m+1}-a^{m+1}$ since the integer is there, $ca+d{a}^m+ncd$
  • Solution:
    • Base Case:
      • $k=1$
      • That's what we're given.
    • Induction Hypothesis and Step:
      • Assume that $a^m\equiv b^m(\mathrm{mod}n)$ for some $m\in \mathbb{N}$ (eminem)
      • $a\cdot a^m\equiv b\cdot b^m(\mathrm{mod}n)$
      • $a^{m+1}\equiv b^{m+1}(\mathrm{mod}n)$
      • Done
• 3
  • Show by induction $\prod _{i=2}^n(1-\frac{1}{i^2})=\frac{n+1}{2n}$
  • Solution:
    • Base Case:
      • $n=2$
      • $\prod _{i=2}^2(1-\frac{1}{2^2})$
      • $\prod _{i=2}^2(1-\frac{1}{4})$
      • $\prod _{i=2}^2\left(\frac{3}{4}\right)$
      • $\frac{n+1}{2n}$
      • $\frac{2+1}{2(2)}$
      • $\frac{3}{4}$
      • Works
    • Induction Step:
      • Assume $\prod _{i=2}^k(1-\frac{1}{k^2})=\frac{k+1}{2k}$ for some $k\in \mathbb{N}:k{\ge }_2$
      • $\prod _{i=2}^{k+1}(1-\frac{1}{k^2})=\prod _{i=2}^k(1-\frac{1}{k^2})\cdot 1-\frac{1}{(k+1{)}^2}$
      • Use $\text{IH}$ to sub it in.
      • $\frac{k+1}{2k}\cdot \frac{(k+1{)}^2-1}{(k+1{)}^2}$
      • Then solve

• Test 2 Question Solutions:
  • Q1:
    • Show that for any $n>2$, $n<p<n!$
    • Proof:
      • Contradiction:
      • Suppose for sake of contradiction, there is no prime between $n$ and $n!$.
        • So they're all composite numbers there.
      • $n!-1$ is composite
      • $p\mid n!-1$
        • Fundtamental Theorem of Arithmetic
        • FTA
      • If the above is true (it is)
      • This means $p<n!$
      • So this means $p\le n$ or else it violates the assumption.
        • Then we know $n\ne (1)\dots (p)\dots (n)$
        • This means $p\mid n!$ and $p\mid n!-1$
        • Then $p\mid n!-(n!-1)$
        • So $p\mid 1$, which is a contradiction.

• Show that the well-ordering principle is a result of induction.
  • The well-ordering principle just says there is a smallest number in any set $S\subseteq \mathbb{N}$
  • Induction says if $P(1)$ is true then $P(n)⟹P(n+1)$ then $\mathrm{\forall }n\in \mathbb{N},P(n)$ is true.
  • Suppose $\mathbb{N}=\{\dots ,a_0,1,2,\dots \}$, (contradiction)
  • $P(1)$