MAT102 Tutorial W9B

102_F2025_Tutorial8.pdf

• 1
  • For any $p>3$ where $p$ is prime, show that $24\mid p^2-1$
  • $p$ is prime so then $24\nmid p$
  • $(p^2-1)=(p+1)(p-1)$
  • $24\mid (p+1)(p-1)$
  • $24k=(p+1)(p-1)$ for some $k\in \mathbb{Z}$
    • For any $3$ consecutive numbers, you can say that $3$ divides at least one of them. As you go through mod, you can see how it works.
    • $3\mid p-1$
      $3\mid p+1$
    • but $3\nmid p$ because $p$ is odd
  • Case $3\mid p-1$
    • If $p\mid ab$ then $p\mid a$ or $p\mid b$
    • $p-1=3k$
    • $2\mid 3k$ so $2\mid 3$ or $2\mid k$
    • $2\nmid 3$ so $2\mid k$
    • So $k$ is even
    • $p-1=2\cdot 3m$ for $m\in \mathbb{N}$
    • Since $2\mid p+1$ then $2\mid (p-1)+2$
    • $2\mid 2\cdot 3m+2$
    • $2\mid 2(3m+1)$
    • $2(3m+1)=p+1$
    • We know that $(p-1)(p-1)=2(3m)(2(3m+1))$
    • We have $3m$ and $3m+1$
    • So if $m$ is even, then $3m$ is even and $3m+1$ is odd and vice versa
    • So one of them is even
    • $(p-1)(p-1)=(2)(2)(3)(2\cdot \dots )$
    • We keep on factoring until we get $24$
• 2
  • a
    • Find the multiplicative inverse of $5(\mathrm{mod}7)$
    • We know that $7$ is prime so clearly there is some multiplicative inverse: $gcd(5,7)=1$
    • $5\cdot x\equiv 1(\mathrm{mod}7)$
    • $7\mid 1-5x$
    • Try solutions from ${\mathbb{Z}}_7$
    • $7\mid 1-5(3)$
    • $7\mid -14$
      • This works
    • So the multiplicative inverse is $[3{]}_7$
    • If there are a lot of potential solutions, then you need to use euclidean algorithm.
  • b
    • Find the integer $x$ such that $5x+3\equiv 2(\mathrm{mod}7)$
    • $7\mid -1-5x$
    • Plug in solutions from ${\mathbb{Z}}_7$
    • $7\mid -1-5(4)$
    • $7\mid -21$
    • So $x=4$

    ---

    • $5x\equiv -1(\mathrm{mod}7)$
    • By part a), $5\cdot 3\equiv 1(\mathrm{mod}7)$
    • so $5(-3)\equiv -1(\mathrm{mod}7)$
    • So a solution is $-3_7$
    • $-3(\mathrm{mod}7)=4$
    • $x=4$
  • c
    • Solve the system $y\equiv 3(\mathrm{mod}5)$ and $y\equiv 2(\mathrm{mod}7)$
    • Find solutions for $y\equiv 3(\mathrm{mod}5)$
    • $5\mid 3-y$
    • $7\mid 2-y$
    • $y\equiv 3(\mathrm{mod}5)$
      • $5\mid 3-y$
      • $5k=3-y$
      • $y=-5k+3$
    • $y\equiv 2(\mathrm{mod}7)$
      • $7\mid 2-y$
      • $7k=2-y$
    • Sub in:
      • $5k+3\equiv 2(\mathrm{mod}7)$
      • By part b), $x\equiv 4(\mathrm{mod}7)$
• Example:
  • $a,b,c,d\in {\mathbb{Z}}_n$
  • $a\equiv b(\mathrm{mod}n)$
  • $c\equiv d(\mathrm{mod}n)$
  • We can have any linear combination of the two congruencies
• 3
  • 1
    • Find $7^{100}(\mathrm{mod}11)$
    • Use FLT
    • $a^{p-1}=1(\mathrm{mod}p)$
    • $11$ is prime
    • $7^{11-1}\equiv 1(\mathrm{mod}11)$
    • $7^{10}\equiv 1(\mathrm{mod}11)$
    • $7^{100}=(7^{10}{)}^{10}=(1{)}^{10}(\mathrm{mod}11)\equiv 1(\mathrm{mod}11)$
  • 2
    • Find $5^{34}+{12}^{35}(\mathrm{mod}17)$
    • $17$ is prime
    • $a^{p-1}=1(\mathrm{mod}p)$
    • $5^{16}\equiv 1(\mathrm{mod}17)$
    • ${12}^{16}\equiv 1(\mathrm{mod}17)$
    • $5^{34}=(5^{2(16)+2})=(5^2)(5^{16}{)}^2$
      • $\equiv (5^2)(1{)}^2$
      • $25(\mathrm{mod}17)=8$
    • ${12}^{35}\equiv {12}^{2(16)+3}\equiv (12{)}^3({12}^{16}{)}^2\equiv (12{)}^3(1)\equiv 1728(\mathrm{mod}17)$
    • $1700+28\equiv 9(\mathrm{mod}17)$