The number leaves remainder when divided by . Find the remainder of when divided by , , , and .
Problem 2 (10 points)
Solve the equation in integers: .
Problem 3 (10 points)
How many (non-oriented) graphs with vertices are there if it is given that admits a Eulerian path, and has no loops? Consider isomorphic graphs as the same graph. In other words, if you can obtain one graph from another by relabeling the vertices, they are considered to be the same graph. Explain your answer.
Problem 4 (10 points)
Prove that the number is a multiple of .
Problem 5 (13 points)
Can the following equality
be true if the letters are substituted for non-zero elements in ? Different letters correspond to different elements.
What about the equality
with the condition that the letters are now substituted for all elements in ?
Problem 6 (15 points)
Show that if and is prime, then is odd.
Problem 7 (15 points)
Solve the equation in integers: .
Problem 8 (15 points)
Prove that, for all integers ,
Problem 9 (20 points)
Let be a prime number greater than . Prove that is divisible by .
Problem 10 (20 points)
Consider a planar graph with vertices and edges. Show that the average degree of is strictly less than . Recall that the average of a family of numbers is defined as .
Problem 11 (25 points)
Consider the cube — a regular polyhedron in . This problem is devoted to the group of all symmetries of the cube. Denote by the rotation counterclockwise (looking from the top) around the vertical axis by . Denote by the rotation counterclockwise (looking from the right) around the blue horizontal axis by .
Every element of the group can be thought of as a permutation of the set of vertices of the cube. Assume the vertices of the cube are labeled as on the picture. Then every element of can be described by an element of , the permutation group on elements.
Rewrite the element as a permutation. Rewrite the element as a permutation.
Consider the elements and . Compute these elements and write the answers as permutations. You can either compute the product geometrically or use permutation multiplication. What do you observe?
What is the inverse element of ? Write your answer as a permutation.
r
s
1234
5678
Problem 12 (30 points)
Prove that for any sets or , if then either or .
Problem 13 (30 points)
Consider the set defined as all elements where . The new element is defined to satisfy the condition . Addition is defined in the following way: , and the result lies in as it is written as an integer added to an integer times . Multiplication is defined as . In other words, the operations are defined as to follow the intuition of the notation: we added a new number to the integers that we want to be able to add and multiply with the integers.
Prove that is still the neutral element for multiplication: in other words, .
An element is called unit if it is invertible with respect to multiplication. Which elements are invertible with respect to multiplication in ? In other words, for which there exists an such that ?
An element in is called prime if it is not and cannot be written as a product of two non-unit elements. Show that the fundamental theorem of arithmetic does not hold in .