Die wöchentlichen Übungsaufgaben können jeweils Dienstag abends von dieser Seite heruntergeladen werden, und die Lösungen können (soweit nicht anders angegeben) jeweils in der darauf folgenden Woche Dienstag zu Beginn der Übungen zur Korrektur abgegeben werden.

Übungsblätter

1 2 3 4 5 6 7 8 9 10 11 12
\(\newcommand {\mat}[4] {\left(\begin{smallmatrix}{#1}&{#2}\\{#3}&{#4}\end{smallmatrix}\right)}\) \(\newcommand {\C} {{\mathbb C}}\) \(\newcommand {\E} {{\mathbb E}}\) \(\newcommand {\F} {{\mathbb F}}\) \(\newcommand {\Pro} {{\mathbb P}}\) \(\newcommand {\Q} {{\mathbb Q}}\) \(\newcommand {\R} {{\mathbb R}}\) \(\newcommand {\Z} {{\mathbb Z}}\) \(\newcommand {\P}[1] {{\mathbb P}^{#1}}\) \(\newcommand {\sym}[1] {{\operatorname{#1}}}\) \(\newcommand {\SL}[1] {{\sym{SL}(2,#1)}}\) \(\newcommand {\hil}[3] {\left({#2},{#3}\right)_{#1}}\) \(\newcommand {\leg}[2] {\left(\tfrac{#1}{#2}\right)}\)

Übungsaufgaben zur Elementaren Zahlentheorie 2014 - Blatt 12

Abgabetermin: Di 8. Juli 2014 zu Beginn der Übung.

  1. For \(n\in \Z_{\geq 0}\), compute \(\sym{gcd}(9n+15,4n+7)\).
  2. For \(n\in \Z_{\geq 0}\), show that \(\sym{gcd}(n^2,2n+1)=1\).

Let \(a\in \Z\), \(a\gt2\) and \(n\in \Z_{\gt 1}\).

  1. Show that \(a^n-1\) is not a prime.
  2. Show that if \(2^n-1\) is a prime then \(n\) is a prime.

Let \(n\in \Z_{\geq 0}\).

  1. Show that \(2^{3n+5}+3^{n+1}\) is divisible by \(5\) but not by \(10\).
  2. Show that \(30\) divides \(n^5-n\).

Solve the following systems of congruences:
1. \( \left\{ \begin{matrix} n\equiv 3 \bmod 37\\ n \equiv 4 \bmod 52 \end{matrix} \right. \)
2. \( \left\{ \begin{matrix} n\equiv 21 \bmod 12\\ n \equiv 12 \bmod 21 \end{matrix} \right. \)
3. \( \left\{ \begin{matrix} n\equiv 2 \bmod 2\\ n \equiv 3 \bmod 3\\ n \equiv 4 \bmod 4 \end{matrix} \right. \)

  1. Compute \(\varphi(1982)\) and \(\varphi(1998)\).
  2. Show that if a prime \(p\) divides \(n\) (resp. \(p^2\vert n\)) then \(p-1\) divides \(\varphi(n)\) (resp. \(p(p-1)\) divides \(\varphi(n)\)).
  3. determine all \(n\in \Z_{\gt0}\) such that \(\varphi(n)<10\).

  1. What is the last digit of \(333^{333}\).
  2. What are the remainders of the euclidian division of \(200^{100}\) and \(21^{22^{23}}\) by \(7\).

  1. Solve the equation \(x^2+4x-1=0\) over \(\F_{11}\).
  2. Solve the equation \(x^2+6x-13=0\) over \(\Z/21\Z\).
  3. Solve the equation \(x^2+3x+2=0\) over \(\Z/6\Z\).
  4. Solve the equation \(x^2+4x+6=0\) over \(\Z/9\Z\).

Let \(p\) prime such that \(p>5\).

  1. Show that \(3\) is a quadratic residue modulo \(p\) if and only if \(p\equiv \pm 1 \bmod 11\).
  2. Show that \(5\) is a quadratic residue modulo \(p\) if and only if \(p\equiv \pm 1 \bmod 5\).
  3. State conditions on \(p\) for \(15\) being a quadratic residue modulo \(p\).

Describe the set of prime numbers such that \[ \# \left\{ x : 0\leq x \lt p, x^2+3x+1=0 \right\} =2. \]

For which prime numbers the equation \(x^2+36x+1\equiv 0 \bmod p\) has solutions ?

  1. Do \(m=23\) and \(m=41\) have primitive roots? If yes, give one, respectively.
  2. Show that \(2\) is a primitive root modulo \(101\).
  3. What is the order of \(3\) modulo \(101\)? Is it a primitive root modulo \(101\)?

  1. Show that \(2\) is a primitive root modulo \(53\).
  2. Find all the (integral) solutions of \(2^{n}\equiv 22 \bmod 53\).

Let \(p=2^{2^n}+1\) with \(n\in \Z_{\geq 1}\).

  1. Assume that \(p\) is a prime.
    1. Show that \(g\) generates \((\Z/p\Z^*)\) if and only if \(\genfrac(){}{0}{g}{p}=-1\).
    2. Show that \(3\) generates \((\Z/p\Z^*)\).
  2. Now we do not assume that \(p\) is a prime but that \(3^{(p-1)/2}\equiv -1 \bmod p\). Show that \(p\) is a prime.
(This is the Pépin's test for primality of Fermat's numbers.)

Let \(f\) be the arithmetic function defined by \(f(n)=(-1)^{n+1}\).

  1. Show that \(f\) is multiplicative but not strongly multiplicative.
  2. Let \(g\) be the inverse of \(f\) for the Dirichlet's product. Compute \(g(p^a)\) for a prime \(p\) and \(a\in \Z_{\geq 0}\) and deduce \(g(n)\) for all \(n\in \Z_{\geq 0}\).

Let \(\sigma(n)=\sum_{d\vert n} d\). For \(n\in \Z_{\gt0}\) show that \(\sigma(3n-1)\) is a multiple of 3.

Solve the following system of congruences: \[ \left\{ \begin{matrix} 3x+4y\equiv 7 \bmod 11\\ 2x+5y\equiv 5 \bmod 11\\ \end{matrix} \right. \]

Find all the rational solutions \((x,y)\) of \(x^2+3xy+2y^2=1\).