Found problems: 18
Find all odd integers $n$ for which $\frac{2^{\phi (n)}-1}{n}$ is a perfect square.
For an integer $ n \geq 2 $, let $ s (n) $ be the sum of positive integers not exceeding $ n $ and not relatively prime to $ n $.
a) Prove that $ s (n) = \dfrac {n} {2} \left (n + 1- \varphi (n) \right) $, where $ \varphi (n) $ is the number of integers positive cannot exceed $ n $ and are relatively prime to $ n $.
b) Prove that there is no integer $ n \geq 2 $ such that $ s (n) = s (n + 2021) $
Let $a$ be a positive real number. Prove that
a) There exists $n\in \mathbb{N}$ with $\frac{\sigma(\varphi(n))}{\varphi(\sigma(n))} > a$.
b) There exists $n\in \mathbb{N}$ with $\frac{\sigma(\varphi(n))}{\varphi(\sigma(n))} < a$.
(As usual, $\sigma(n) = \sum_{d\mid n} d$ and $\varphi(n)$ is the number of integers $1\le m\le n$ which are coprime with $n$.)
Proposed by [i]Deniz Can Karaçelebi[/i]
Given an integer $n > 1$, let $1 = a_1 < a_2 < \cdots < a_t = n - 1$ be all positive integers less than $n$ that are coprime to $n$. Find all $n$ such that there is no $i \in \{1, 2, \ldots , t - 1\}$ satisfying $3 | a_i + a_{i+1}$.
Let $c \ge 2$ be a fixed integer. Let $a_1 = c$ and for all $n \ge 2$ let $a_n = c \cdot \phi (a_{n-1})$. What are the numbers $c$ for which sequence $(a_n)$ will be bounded?
$\phi$ denotes Euler’s Phi Function, meaning that $\phi (n)$ gives the number of integers within the set $\{1, 2, . . . , n\}$ that are relative primes to $n$. We call a sequence $(x_n)$ bounded if there exist a constant $D$ such that $|x_n| < D$ for all positive integers $n$.
Prove that the following inequality holds with the exception of finitely many positive integers $n$:
\[\sum_{i=1}^n\sum_{j=1}^n gcd(i,j)>4n^2.\]
Given a real number $\alpha$ and consider function $\varphi(x)=x^2e^{\alpha x}$ for $x\in\mathbb R$. Find all function $f:\mathbb R\to\mathbb R$ that satisfy: $$f(\varphi(x)+f(y))=y+\varphi(f(x))$$ forall $x,y\in\mathbb R$
Find all natural numbers $n$ for which $1^{\phi (n)} + 2^{\phi (n)} +... + n^{\phi (n)}$ is coprime with $n$.
Find all odd integers $n$ for which $\frac{2^{\phi (n)}-1}{n}$ is a perfect square.
Find all integers $a$ such that there are infinitely many positive integers $n$ such that $n$ divides $\phi(n)!+a$.
For each positive integer $x$, let $\varphi(x)$ be the number of integers $1 \leq k \leq x$ that do not have prime factors in common with $x$. Determine all positive integers $n$ such that there are distinct positive integers $a_1,a_2, \ldots, a_n$ so that the set: $$S = \{a_1, a_2, \ldots, a_n, \varphi(a_1), \varphi(a_2), \ldots, \varphi(a_n)\}$$ Have exactly $2n$ consecutive integers (in some order).
Given a positive integer $n \geq 2$, whose canonical prime factorization is $n = p_1^{\alpha_1}p_2^{\alpha_2} \ldots p_k^{\alpha_k}$, we define the following functions:
$$\varphi(n) = n\bigg(1 -\frac{1}{p_1}\bigg) \bigg(1 -\frac{1}{p_2}\bigg) \ldots \bigg(1 -\frac {1}{p_k}\bigg) ; \overline{\varphi}(n) = n\bigg(1 +\frac{1}{p_1}\bigg) \bigg(1 +\frac{1}{p_2}\bigg) \ldots \bigg(1 + \frac{1}{p_k}\bigg)$$
Consider all positive integers $n$ such that $\overline{\varphi}(n)$ is a multiple of $n + \varphi(n) $.
(a) Prove that $n$ is even.
(b) Determine all positive integers $n$ that satisfy this property.
Find all positive integers $n$, such that $n$ is a perfect number and $\varphi (n)$ is power of $2$.
[i]Note:a positive integer $n$, is called perfect if the sum of all its positive divisors is equal to $2n$.[/i]
Find all odd integers $n$ for which $\frac{2^{\phi (n)}-1}{n}$ is a perfect square.
On the grid plane all possible broken lines with the following properties are constructed:
each of them starts at the point $(0, 0)$, has all its vertices at integer points, each linear segment goes either up or to the right along the grid lines. For each such broken line consider the corresponding [i]worm[/i], the subset of the plane consisting of all the cells that share at least one point with the broken line. Prove that the number of worms that can be divided into dominoes (rectangles $2\times 1$ and $1\times 2$) in exactly $n > 2$ different ways, is equal to the number of positive integers that are less than n and relatively prime to $n$.
(Ilke Chanakchi, Ralf Schiffler)
Let $f(n)$ be number of numbers $x \in \{1,2,\cdots ,n\}$, $n\in\mathbb{N}$, such that $gcd(x, n)$ is either $1$ or prime. Prove
$$\sum_{d|n} f(d) + \varphi(n) \geq 2n$$
For which $n$ does equality hold?
The notation $\phi (n)$ is the number of positive integers smaller than $n$ and coprime with $n$, $\pi (n)$ is the number of primes that do not exceed $n$. Prove that for any natural number $n > 1$, we have
$$\phi (n) \ge \frac{\pi (n)}{2}$$
On the grid plane all possible broken lines with the following properties are constructed:
each of them starts at the point $(0, 0)$, has all its vertices at integer points, each linear segment goes either up or to the right along the grid lines. For each such broken line consider the corresponding [i]worm[/i], the subset of the plane consisting of all the cells that share at least one point with the broken line. Prove that the number of worms that can be divided into dominoes (rectangles $2\times 1$ and $1\times 2$) in exactly $n > 2$ different ways, is equal to the number of positive integers that are less than n and relatively prime to $n$.
(Ilke Chanakchi, Ralf Schiffler)