MAT102 Tutorial W8

• 1

  • a
    • Find $5^{12}(\mathrm{mod}13)$
    • FLT
    • $a^{p-1}\equiv 1(\mathrm{mod}p)$
    • 13 is prime
    • $5^{12}(\mathrm{mod}13)=1$
  • b
    • Find $5^{1000}(\mathrm{mod}13)$
    • $p=13$
    • $a=5$
    • $a\nmid p$
    • $(5^{10}{)}^{100}(\mathrm{mod}13)$
    • $5^{12}\equiv 1(\mathrm{mod}13)$
    • $5^{12\cdot 83+4}\equiv 1(\mathrm{mod}13)$
    • $1000=12\cdot 83+4$
    • $5^{1000}=5^{12\cdot 83+4}=(5^{12}{)}^{83}\cdot 5^4$
    • $(5^{12}{)}^{83}\equiv 1^{83}\equiv 1(\mathrm{mod}13)$
    • $5^{1000}\equiv (5^{12}{)}^{83}\cdot 5^4\equiv 1\cdot 5^4\equiv 5^4(\mathrm{mod}13)$
    • $5^2=25\equiv 25-13-13\equiv -1(\mathrm{mod}13)$ or $25\equiv 12(\mathrm{mod}13)$
    • $5^4=(5^2{)}^2\equiv (-1{)}^2(\mathrm{mod}13)$
    • $5^4\equiv 1(\mathrm{mod}13)$
    • $5^4=625$. $625÷13=48$ with a remainder of $1$.

• 2

  • Multiplicative Inverse for $29$ in ${\mathbb{Z}}_{43}$
  • $29\cdot \frac{1}{29}\equiv 1(\mathrm{mod}43)$

• 3 Are these fields?:

  • $\mathbb{R}\setminus \mathbb{Q}$
    • Additive Inverse

• Solutions

• 1

  • b
    • Pull out as many factors of 12 as we can
    • $5^{1000}\equiv (5^{12}{)}^{83}\cdot 5^4(\mathrm{mod}13)$
    • $\equiv 5^2\cdot 5^2(\mathrm{mod}13)\equiv {12}^2(\mathrm{mod}13)$
    • $(-1{)}^2(\mathrm{mod}13)$
    • $\equiv 1$
    • $\frac{25}{13}=1\cdot 13+12$
      • $12\equiv -1(\mathrm{mod}13)$

• 2

  • Solve for a
  • $29a\equiv 1(\mathrm{mod}45)$
  • This also means
    • $29x+43y=1$
  • ${\mathbb{Z}}_{43}\times \varphi (43)$
  • Instead of doing that, do euclid's algo on the equation
  • $29x+43y=1$
  • $\{\begin{array}{ll}43& =29(1)+14\\ 29& =19(2)+1\end{array}$
  • $1=29-14(2)$
  • $1=29-(2)(43-29(1))$
  • $1=29(3)-43(2)$
  • $1=29(3)+43(-2)$
  • $x=3,y=-2$

• 3

  • a
    • $\mathbb{R}\setminus \mathbb{Q}$
    • No because no $0$ or additive identity.
  • b
    • $\mathbb{Q}[\sqrt{n}]=\{a+b\sqrt{n}:a,b\in \mathbb{Q}\}$, $n\in \mathbb{N}$ where $n$ is a non-perfect square.
    • Is a field
    • If $\mathbb{Q}[\sqrt{n}]\subseteq \mathbb{R}$ then we automatically get commutativity and associativity
    • $0=0+0\sqrt{n}$
    • $1=1+0\sqrt{n}$
    • Closure
      • Additive
        • $a+b\sqrt{n}+c+d\sqrt{n}$
        • $(a+c)+(b+d)\sqrt{n}$
        • This is in $\mathbb{Q}$
      • Multiplicative
        • $(a+b\sqrt{n})(c+d\sqrt{n})$
        • $ac+ad\sqrt{n}+dc\sqrt{n}+bdn$
        • $ac+bdn+(ad+bc)\sqrt{n}$
        • This is in $\mathbb{Q}$
    • Inverse
      • Additive
        • $a\in \mathbb{Q}$ then $-a\in \mathbb{Q}$
        • $b\in \mathbb{Q}$ this means $-b\in \mathbb{Q}$
        • Thus
          • for any $a,b$
          • $a+b\sqrt{n}-a-b\sqrt{n}=0$
          • So this works
      • Multiplicative
        • $(a+b\sqrt{n})(a-b\sqrt{n})$
        • $a^2-b^{2}n$
        • If $a^2-b^{2}n=0$
          • Then $a^2=b^{2}n$
          • $a=b\sqrt{n}$
          • If it's a non-perfect square, then rational can't be irrational?
          • What
          • Not working?
  • c
    • $\{0,1,x,y\}$
    • No multiplicative inverse
    • $x\cdot x^{-1}$ = $1$
    • But $1\in C$ already. So we can't have duplicates. So it won't work.

• If we have $b^2\mid a^2⟹b\mid a$

• Proof:

  • We know that
  • $a^2=p_1^{2k_1}{p}_2^{2k_2}\dots p_n^{2k_n}$ by fta
  • Every square has an even power
  • $b^2=p_1^{2{\ell }_1}{p}_2^{2{\ell }_2}\dots p_n^{2{\ell }_n}$
  • Any $2k_i\le 2{\ell }_i$
  • So if we $\sqrt{b^2}$ ans $\sqrt{a^2}$
  • we get $k_i\le {\ell }_i$

• Another thing to remember is:

  • Show that $\sqrt{pq}$ is irrational
  • $p,q$ are two prime numbers.
  • Proof:
    • Contradiction
    • Assume not, that is $\sqrt{pq}=\frac{a}{b}$ where $a,b\in \mathbb{Z}$ and $gcd(a,b)=1$
    • $pq=\frac{a^2}{b^2}$
    • $a^2=p_1^{2k_1}{p}_2^{2k_2}\dots p_n^{2k_n}$ all even powers
    • $b^2=p_1^{2{\ell }_1}{p}_2^{2{\ell }_2}\dots p_n^{2{\ell }_n}$ all even powers
    • $pq{b}^2=a^2$
    • Any square number has all even powers
    • But $pq$ would have odd prime powers, so that's the contradiction.
    • Same in readings prove $\sqrt{2}$ is irrational

• Practice

  • Euclid's lemma
    • $a^{p-1}\equiv 1(\mathrm{mod}p)$
    • $a^2\equiv b^2(\mathrm{mod}p)⟺a\equiv b$ or $a\equiv -b(\mathrm{mod}p)$
    • Prove the above
  • Euclidean Algorithm