TU Wien:Discrete Mathematics VO (Stufler)/Written Exam 2025-06-27

1. Number Theory

a) For which integers m is the group $\mathbb {Z} /<m>^{\times }$ cyclic?

b) Compute with Euler's totient function the number of elements in $\mathbb {Z} /<100>^{\times }$

c) Compute $7^{100}mod40$

2. Combinatorics

Show that each set of integers with 5 elements has 3 elements whose sum is divisible by 3.

3. Finite fields

Consider the field $\mathbb {F} _{2}[x]/<f>$ with $f=X^{4}+X+1$

a) Show that f is irreducible.

b) Using euclids algorithm, determine the inverse of $X^{3}+X+1$

4. Graph Theory

Show that every simple graph with $deg(v)\geq 3$ for all vertices has a cycle with length at least 4.