Problems

The prime factorization of the number \(b\) is \(2 \times 5^2 \times 7 \times 13^2 \times 17\). The prime factorization of the number \(c\) is \(2^2 \times 5 \times 7^2 \times 13\). Is the first number divisible by the second one? Is the product of these two numbers, \(b \times c\), divisible by \(49000\)?

Find all the prime numbers \(p\) such that there exist natural numbers \(x\) and \(y\) for which \(p^x = y^3 + 1\).

Determine all prime numbers \(p\) such that \(5p+1\) is also prime.

A natural number \(p\) is called prime if the only natural divisors of \(p\) are \(1\) and \(p\). Prime numbers are building blocks of all the natural numbers in the sense of the The Fundamental Theorem of Arithmetic: for a positive integer \(n\) there exists a unique prime factorization (or prime decomposition) \[n = p_1^{a_1}p_2^{a_2}...p_r^{a_r}.\] Today we will explore how unusual prime numbers are.
Essentially there is only one way to write an integer number as a product of prime numbers, where some of the prime numbers in the product can appear multiple times.

Find all natural numbers \(n\) for which there exist integers \(a,b,c\) such that \(a+b+c = 0\) and the number \(a^n + b^n + c^n\) is prime.

Find all the prime numbers \(p\) such that the number \(2p^2+1\) is also prime.

A graph is a finite set of points, some of which are connected with line segments. The points of a graph are called vertices. The line segments are called edges. In this problem set we only consider graphs in which every pair of vertices is connected with one or zero edges.

In a mathematical problem, one may use vertices of a graph to represent objects in the problem, i.e. people, cities, airports, and edges of the graph represent relations between the objects such as mutual friendship, railways between cities, plane routes. As you will see in the examples below, representing the initial problem as a graph can considerably simplify the solution.

A graph is called Bipartite if it is possible to split all its vertices into two groups in such a way that there are no edges connecting vertices from the same group. Find out whic of the following graphs are bipartite and which are not:

Show that a bipartite graph with \(n\) vertices cannot have more than \(\frac{n^2}{4}\) edges.

In a graph \(G\), we call a matching any choice of edges in \(G\) in such a way that all vertices have only one edge among chosen connected to them. A perfect matching is a matching which is arranged on all vertices of the graph.
Let \(G\) be a graph with \(2n\) vertices and all the vertices have degree at least \(n\) (the number of edges exiting the vertex). Prove that one can choose a perfect matching in \(G\).