Bboyjordan's Blog

19/12/2011

List of funny problems (3rd)

Filed under: Mathematical matters — bboyjordan @ 7:31 PM

Problem25- Maybe Fermat primes are infinte?

Show that $\displaystyle \lim_{n\to +\infty}{\sigma_{-1}(2^{2^n}+1)}=1$ .
Solution. For every positive integer $\displaystyle m=\prod_{1\le i\le \omega(m)}{p_i^{\alpha_i}}$ we have by definition $\sigma_{-1}(m)=\displaystyle \sum_{d\mid m}{d^{-1}}=\prod_{1\le i\le \omega(m)}{\left(\sum_{0\le j \le \alpha_i}{p^{-j}}\right)}= \prod_{1\le i\le \omega(m)}{\frac{p-p^{-\alpha_i}}{p-1}}$ .

It means that for $m=2^{2^n}+1$ we have $\sigma_{-1}(2^{2^n}+1)=\displaystyle \prod_{p_i\mid 2^{2^n}+1}{\frac{p_i-p_i^{-\alpha_i}}{p_i-1}} < \prod_{p_i\mid 2^{2^n}+1}{\frac{p_i}{p_i-1}}= \prod_{p_i\mid 2^{2^n}+1}{\left(1+\frac{1}{p_i-1}\right)}$ .

Note now that if a prime $p_i \mid 2^{2^n}+1$ then $\text{ord}_{p_i}=2^{n+1}$ ; but since $\text{ord}_{p_i}(2)\mid \varphi(p_i)=p_i-1$ then there exists a positive integer $k_i>0$ such that $p_i=k_i2^{n+1}+1$ .

Also this trivial inequality holds: $2^{(n+1)2^n}>2^{2^n}+1=\displaystyle \prod_{p_i\mid 2^{2^n}+1}{p_i^{\upsilon_{p_i}(2^{2^n}+1)}} \ge \prod_{1\le i\le \omega(2^{2n}+1)}{p_i}> 2^{(n+1)\omega(2^{2^n}+1)}$ : so $\omega(2^{2^n}+1)<2^n$ .

Summing up, $\sigma_{-1}(2^{2^n}+1)<\displaystyle \prod_{1\le i\le \omega(2^{2^n}+1)}{\left(1+\frac{1}{p_i-1}\right)}$ $= \displaystyle \prod_{1\le i\le \omega(2^{2^n}+1)}{\left(1+\frac{1}{k_i2^{n+1}}\right)} \le \prod_{1\le i\le \omega(2^{2^n}+1)}{\left(1+\frac{1}{i2^{n+1}}\right)}$ .

Extendig this product, we have $\sigma_{-1}(2^{2^n}+1)<$ $\displaystyle \sum_{0\le i\le \omega(2^{2^n}+1)}\left(\frac{1}{2^{i(n+1)}}\left(\sum_{1\le x_1<x_2<\ldots<x_i\le \omega(2^{2^n}+1)}{\frac{1}{x_1x_2\ldots x_i}}\right) \right)$ $\displaystyle < \sum_{0\le i\le 2^n}\left(\frac{1}{2^{i(n+1)}}\left(\sum_{1\le x_1<x_2<\ldots<x_i\le 2^n}{\frac{1}{x_1x_2\ldots x_i}}\right) \right)$ $< \displaystyle \sum_{0\le i\le 2^n}\left(\frac{1}{2^{i(n+1)}}\left(\sum_{1\le x_1\le x_2\le \ldots\le x_i\le 2^n}{\frac{1}{x_1x_2\ldots x_i}} \right)\right)$
$\displaystyle = \displaystyle \sum_{0\le i\le 2^n}\left(\frac{1}{2^{i(n+1)}}\left(\sum_{1\le j\le 2^n}{j^{-1}} \right)^i\right)$ .

For every integer $y\ge 2$ it’s also true that $\displaystyle \sum_{1\le j\le y}{j^{-1}}<1+\int_1^y{x^{-1}dx}=1+\ln(y)$ .

Then we can say that there exists a positive constant $C>0$ such that $\displaystyle \sum_{1\le j\le 2^n}{j^{-1}}< Cn$ .

Turning back to our problem, we proved that $\displaystyle \sigma_{-1}(2^{2^n}+1)<\displaystyle \sum_{0\le i\le 2^n}\left(\frac{1}{2^{i(n+1)}}\left(\sum_{1\le j\le 2^n}{j^{-1}} \right)^i\right)$ $\displaystyle < \sum_{0\le i\le 2^n}{\left(\frac{Cn}{2^{n+1}}\right)^i}$ $\displaystyle< \sum_{0\le i\le \infty}{\left(\frac{Cn}{2^{n+1}}\right)^i}=$ $\displaystyle \frac{2^{n+1}}{2^{n+1}-Cn}$ .

Now since for every $\epsilon>0$ the following inequality $\displaystyle 2^{n+1}\left(1-\frac{1}{1+\epsilon} \right)>Cn$ holds definitively, then we finished, indeed:

$\displaystyle \lim_{n\to +\infty}\sigma_{-1}(2^{2^n}+1)< \displaystyle \frac{2^{n+1}}{2^{n+1}-C\ln(n)} < 1+\epsilon$ . []

Leave a Comment

05/03/2011

Fundamental theorem of Asset Pricing

Filed under: Mathematical matters — bboyjordan @ 6:48 PM

Abstract

In $1973$ Fisher Black and Myron Scholes published their pathbreaking paper [Ref: The pricing of options and corporate liabilities, Journaly of Political Economy] on option pricing, where the main idea (attribuited to Rober Merton) is the use of trading in continous time and the notion of arbitrage. The simple and economically very convincing “principle of no-arbitrage” allows one to derive, in certain mathematical model of financial markets (such as Samuelson model, the so-called “Black-Scholes model” based on geometric Brownian motion), unique prices for options and other contingent claims. The main role of no-arbitrage has been started to be studied later, in the late seventies (see Harrison, Kreps and Pliska), and it can be summarized in the “Fundamental theorem of asset pricing”(the name was given by Ph.Dybvig and S.Ross), which is not just a theorem but rather a general principle deeply related with martingale theory. We’ll begin this article with the basic proof of the theorem, as in its first formultion by Harrison and Pliska, under contraints of discrete time and finite $|\Omega|$ (this implies that all the function spaces $L^p(\Omega,\text{F},P)$ are all finite dimensional and isomorphic to $\mathbb{R}^{|\Omega|}$ ). Clearly, these assumption are very restrictive and do not even apply to the very first example of the theory, such as Black-Scholes model ot the much older model considered by L.Bachelier. So we’ll establish some more general version of this theorem, first in a continous time model, and then assuming infinite dimensional spaces: these version are result of a long line of increasingly general research achieved in the past two decades up to nowadays. Loosely speaking, it states that a mathematic model of financial market is free of arbitrage if and only if it is a martingale under an equivalent probability measure (i.e. it has same sets of null measure); it plays a truly fundamental role in the theory of pricing and hedging of derivatives securities (or, synonymously, contingent claim, i.e., element of $L^0(\Omega,\text{F},P)$ ) by no-arbitrage arguments; in this way the relation to martingale theory and stochastic integration opens the gates to the application of a powerful mathematical theory.

The whole essay can now be downloaded here: LF1302108

Leave a Comment

02/03/2011

Elementary cases of Mihailescu Theorem

Filed under: Mathematical matters — bboyjordan @ 4:27 PM

In number theory, Mihailescu theorem is the solution to a old conjecture due to Eugene Charles Catalan (1844). It was proved in April 2002, and it states:

“The unique solution $(x,y,a,b)\in \mathbb{Z}^4$ of $x^a-y^b=1$ with $\min\{x,y,a,b\}>1$ is $(3,2,2,3)$ .”

Since the whole proof uses cylotomic fields, Galois theory, and other non elementary facts, we’ll present here some cases that can be completely solved with basic knowledge:

1- $2\mid b$ .

Consider the equation $x^p-y^q=1$ .

We have to show that, for all integer $x$ , $y^2+1$ is not a perfect non trivial power of another integer, i.e. $y^2+1=x^p$ has no integer solutions in $\mathbb{Z}^2$ except the trivial one $(x,y)=(1,0)$ .

It’s clear that $p=2$ has not non-trivial solution, so from now on we can assume that $p\in \mathbb{P}\setminus\{2\}$ .

If $2\nmid y$ then $2\mid x$ and in particular $8\mid y^2-1=x^p-2$ implies $4\mid \frac{x^p}{2}-1$ , that is $0=\upsilon_2\left( \frac{x^p}{2}\right)= p\upsilon_2(x)-1\ge p-1 \ge 2$ , contradiction. We showed that $y$ is even, and $x$ is odd.

Working now in $\mathbb{Z}[i]$ we have: $(y+i)(y-i)=x^p$ . Since $\text{gcd}(y+i,y-i)=\text{gcd}(y+i,2i)\mid 2$ since $i$ is a unit. It means also that $x^p$ is divisible by $\text{gcd}(y+i,y-i)\mid 2i$ , and it cannot be $2$ since we showed that $x$ has to be odd. In other words, $y+i$ and $y-i$ are both $p-$ power of some complex number in $\mathbb{Z}[i]$ .

So there exist $(y,a,b,p) \in \mathbb{Z}^3\times \left(\mathbb{P}\setminus\{2\}\right)$ such that $y+i=(a+bi)^p=\displaystyle \sum_{0\le j\le p}{\binom{p}{j}a^j(bi)^{p-j}}$ .

Taking only imaginary parts, in the summation we have to consider only even $j$ , that implies: $\displaystyle 1=\sum_{0\le j\le \frac{p-1}{2}}{\binom{p}{2j}a^{2j}b^{p-2j}i^{p-2j-1}}$ , a integer number divisible by $b$ : then $b\mid 1$ , and in particular $b^2=1$ .

Then, it’s equivalent to say that $\displaystyle 1=(-1)^{\frac{p-1}{2}}b\sum_{0\le j\le \frac{p-1}{2}}{\binom{p}{2j}(-a^2)^{j}}$ .

Since $x^p=(a+i)^p(a-i)^p=(a^2+1)^p$ and $x$ must be odd, then $a$ is a even integer. Looking the previous equation in $\mathbb{Z}/4\mathbb{Z}$ , we must have $\displaystyle \sum_{0\le j\le \frac{p-1}{2}}{\binom{p}{2j}(-a^2)^{j}}=1$ , that is equivalent to $a^2\binom{p}{2}=\displaystyle \sum_{2\le j\le \frac{p-1}{2}}{\binom{p}{2j}(-a^2)^{j}}$

Taking in consideration the identity $j(2j-1)\binom{p}{2j}=\binom{p}{2} \binom{p-2}{2j-2}$ , we can say that for all integers $j\ge 2$ the following chain of inequality holds: $\upsilon_2(a^{2j}\binom{p}{2j})=2j\upsilon_2(a)+\upsilon_2(\binom{p}{2j})$ $\displaystyle =2j\upsilon_2(a)+\upsilon_2(\binom{p-2}{2j-2})+\upsilon_2(\binom{p}{2})-\upsilon_2(j)$ $\ge 2j\upsilon_2(a)+\upsilon_2(\binom{p}{2})-\upsilon_2(j)$ $> 2\upsilon_2(a)+\upsilon_2(\binom{p}{2})=\upsilon_2(a^2\binom{p}{2})$ .

It’s enough to conclude that the equation $x^p-y^2=1$ has no non-trivial solution in integers greater than 1.

2- $x=b$ with $\omega(x)=1$ .

If $b$ is a power of $2$ , then there are no solutions, directly by point 1.

Otherwise there exist a prime $p>2$ and a integer $k>0$ such that $x=b=p^k$ ; note now that $(p^k)^a-y^{p^k}=1$ has a solution if and only if $z^p+1=p^t$ for some integer $z>1, t>0$ . Then $(z+1)\left(\frac{z^p+1}{z+1}\right)=p^t$ : it means that both factors are powers of $p$ . But $\upsilon_p\left(\frac{z^p+1}{z+1}\right)=\upsilon_p(z+1)+\upsilon_p(p)-\upsilon_p(z+1)=1$ , and we get a contradiction since:
$\displaystyle p=\frac{z^p+1}{z+1}\ge \frac{z^3+1}{z+1}=z^3-z+1\ge 3z-z+1> z+1 \ge p$ . []

3- $x=b$ with $p^{13} \nmid a$ for all $p\in \mathbb{P}$ .

Since $x-1\mid x^a-1=y^b$ , it’s clear that $\text{rad}(x-1)\mid \text{rad}(y)$ . Directly from point 1, we have that if $2\mid b$ than there are no solutions, so we’ll assume that $b$ is odd. Since $b=x$ , we have that if $(x,y,a,x)$ is a solution then $\omega(x)\ge 2$ , directly from point 2. It means that if $x$ is a (odd) solution, then $x\ge 3\cdot 5$ .

Assume that there exists a prime $p>2$ such that $p\mid x-1$ . Then, we get a contradiction since:
$\displaystyle x=b\le b\upsilon_p(y)=\upsilon_p(y^b)=\upsilon_p(x^a-1)=\upsilon_p(x-1)+\upsilon_p(a)\le$ $\displaystyle \text{log}_p(x-1)+12\le \frac{\ln(x-1)}{\ln(3)}+12$ .

Now $\text{log}_3(14)+12<\text{log}_3(27)+12=15$ ; moreover $\ln(x-1)$ is a concave function (it means, with decreasing derivative function), so the previous inequality will not hold for all integer $x\ge 15$ . And since, for $1\le x\le 14$ there are no solutions, then $x-1$ has to be a power of $2$ .

Let $m\ge 4$ a integer such that $x=2^m+1$ . Then $y$ will be even, and in particular the following inequality holds:

$2^m+1\le x\upsilon_2(y)=\upsilon_2(y^x)=\upsilon_2(y^b)=$ $\upsilon_2(x^a-1)=\upsilon_2(\frac{x^2-1}{2})+\upsilon_2(a)=m+\upsilon_2(a)\le m+12$ .

It’s a contradiction, since the previous inequality is false for all integers $m\ge 4$ . []

Corollary: for all integer $n>1$ define the set $S(n):=\{r\in \mathbb{N}\cap [2,n]: x^r-y^x=1$ has no solutions in integers >1 }. Then $\lim_{n\to +\infty}{\frac{|S(n)|}{n}}>\frac{999}{1000}$ .

Indeed for the inclusion-exclusion principle, it’s true that $\displaystyle \lim_{n\to +\infty}{\frac{|S(n)|}{n}}=\prod_{p\in \mathbb{P}}(1-p^{-13})=\zeta(13)^{-1}$ $\displaystyle =\frac{1}{\sum_{i\in \mathbb{N}_0}{i^{-13}}}>$ $\frac{1}{1+\sum_{i\in \mathbb{N}_0}{2^{i-1}2^{-13i}}}=\frac{1}{1+(2^{13}-2)^{-1}}>\frac{1}{1+2^{-12}}>\frac{999}{1000}$ .

4- $x=b$ .

(Solution by dario2994). Assume that for some $a\ge 3$ there exists a solution $(x,y,a,x)$ ; as before $x$ must be odd and $y$ even. For every odd prime $p$ that divides $y+1$ we have: $a\upsilon_p(x)=\upsilon_p(x^a)=\upsilon_p(y^x+1)=\upsilon_p(y+1)+\upsilon_p(x)$ . It implies $y+1\ge p^{a-1}\ge 3^{a-1}\ge 2^a+1$ , so it’s true also that $x^a=y^x+1>2^{ax}$ , that’s a contradiction for every $x>1$ . So $|S(n)|$ is exactly $n-2$ . []

5- $2\mid a$ and $b\in \mathbb{P}$ .

(Under construction)

6- $y\mid x-1$ .

(Under construction)

Leave a Comment

25/07/2010

List of funny problems (2nd)

Filed under: Mathematical matters — bboyjordan @ 4:59 PM

Problem 16- A bound regarding binomial coefficients

For each $x\in\mathbb{R}\cap (0,1)$ define the binary entropy $H(\cdot): (0,1)\to\mathbb{R} : x\to -x \text{log} _2(x) - (1-x) \text{log} _2(1-x)$ , and let $n>2$ a fixed integer. Show that the following inequality $\displaystyle 2^{nH(\frac{k}{n})}\le (n+1)\binom{n}{k}$ holds for all $k\in \mathbb{Z}\cap [1,n-1]$ .

Solution. Substitute the explicit value of $H(kn^{-1})$ in the inequality, and just regroup to obtain the inequality $\displaystyle \frac{n^n}{k^k(n-k)^{n-k}} \le (n+1)\binom{n}{k}$ . It means that we can reformulate the problem in the equivalent form: “Let $a,b$ be positive integers with sum $c>2$ , then $\displaystyle \frac{a^a}{a!}\cdot \frac{b^b}{b!} \ge \frac{c^c}{(c+1)!}$ ”. So, for every $c$ fixed we obtain that left hand side if this inequality is a function $f(\cdot): \mathbb{Z}\cap [1,c-1]\to \mathbb{Q}$ of the unique variable $a$ , since $\displaystyle f(a):=\frac{a^a(c-a)^{c-a}}{a!(c-a)!}$ . We can show that $f(\cdot)$ attains its minimum at $\displaystyle a=\lfloor \frac{c}{2} \rfloor$ ,so that it will be enough to show that $\displaystyle (c+1)!f(\lfloor \frac{c}{2} \rfloor)\ge c^c$ . Observe also that the function $f(\cdot)$ is symmetric with respect to $\frac{c}{2}$ .

Case1: $c=2C$ for some $C\in\mathbb{N}_0$ . Fix $a \in \mathbb{Z}\cap [1,C-1]$ , then $f(a)\ge f(a+1)$ , that is true if and only if $a^a(2C-a)^{2C-a}\binom{2C}{a}=c!f(a)$ $\ge c!f(a+1)= (a+1)^{a+1}(2C-a-1)^{2C-a-1}\binom{2C}{a+1}$ : it can be rewritten as $\displaystyle \left(1+\frac{1}{2C-a-1}\right)^{2C-a-1}\ge\left(1+\frac{1}{a}\right)^a$ . Now it is well-known that the function $g(x):=(1+x^{-1})^x$ is strictly increasing in $\mathbb{R}\cap [1,+\infty)$ , so that this inequality remains true if and only if $2C-a-1\ge a$ , and in fact by construction $a\le C-1$ . So, for the case $c$ even, we have to show that $\displaystyle \left(\frac{C^C}{C!}\right)^2=f(C)\ge \frac{c^c}{(c+1)!}$ $\displaystyle =\frac{4^C}{2C+1}\cdot \frac{C^{2C}}{(2C)!}$ , that is $\displaystyle \binom{2C}{C}\ge \frac{4^C}{2C+1}$ for all positive integer $C$ .

Case2: $c=2C+1$ for some $C\in\mathbb{N}_0$ . Just repeat the same ideas of previous lines: fix $a \in \mathbb{Z}\cap [1,C-1]$ , then $f(a)\ge f(a+1)$ , that is true if and only if $a^a(2C+1-a)^{2C+1-a}\binom{2C+1}{a}=$ $c!f(a)\ge c!f(a+1)=$ $(a+1)^{a+1}(2C-a)^{2C-a}\binom{2C+1}{a+1}$ : it can be rewritten as $\displaystyle \left(1+\frac{1}{2C-a}\right)^{2C-a}\ge\left(1+\frac{1}{a}\right)^a$ . And, as before, it is enough that $2C-a\ge a$ , and in fact by construction $a\le C-1$ . So, for the case $c$ odd, we have to show that $\displaystyle \frac{C^C(C+1)^{C+1}}{C!(C+1)!}=f(C)$ $\ge\frac{c^c}{(c+1)!}=$ $\displaystyle \frac{(2C+1)^{2C+1}}{(2C+2)!}$ . Now multiply both members to $\displaystyle \frac{(2C)!}{C^C(C+1)^C}$ , and we obtain: $\displaystyle \binom{2C}{C}\ge \frac{(2C+1)^{2C}}{2C^C(C+1)^{C+1}}$ . Set $d:=2C$ and observe the following chain of inequalities: $\displaystyle \frac{(2C+1)^{2C}}{2C^C(C+1)^{C+1}}=$ $\displaystyle \frac{1}{2C+2}\cdot \frac{(2C+1)^{2C}}{C^C(C+1)^{C+1}}$ $\displaystyle <\frac{1}{2C+2}\cdot \frac{(2C+1)^{2C}}{C^C\cdot C^C}$ $\displaystyle =\frac{1}{2C+2}\cdot \left(2+\frac{2}{d}\right)^d$ $\displaystyle <\frac{e\cdot 2^d}{2C+2}=4^C\cdot \frac{e}{2C+2}$ . We have shown that for the case $c$ odd, it is enough to prove that $\displaystyle \binom{2C}{C}\ge 4^C\cdot \frac{e}{2C+2}$ for all positive integer $C$ .

First, let’s verify manually that $k(C):=\binom{2C}{C}$ is greater than $h(C)$ , defined as the maximum between $\frac{2^{2C}}{2C+ 1}$ and $\displaystyle \frac{(2C+1)^{2C}}{2C^C(C+1)^{C+1}}$ for all $C\in \mathbb{Z}\cap [1,11]$ : (C, k(C), h(C)): { (1, 2, 1.3), (2, 6, 3.2), (3, 20, 9.1), (4,70 , 28.4), (5, 252, 93), (6, 924, 315), (7, 3432, 1092), (8, 12870, 3855), (9, 48620, 13797),(10, 184756, 49932),(11, 705432, 182361)}.

Note now that for all real $x>0$ the inequality $\displaystyle \frac{4^x}{2x+1}< \frac{e4^x}{2x+2} <\frac{2^{2x+1}}{x+1}$ holds, so that the whole problem can be summarized in $\displaystyle \binom{2C}{C}\ge \frac{2^{2C+1}}{C+1}$ for all positive integer $C\in \mathbb{Z}\cap [12,+\infty)$ .

Define now the sequence of $\{x_n\}_{n\in\mathbb{N}}$ of positive reals by $\displaystyle x_n:=\int_0^{\pi}{\sin^n(x) dx}$ . It is clear that such sequence is (strictly) decreasing, with $x_0=\pi, x_1=2$ . Integrating two times by part, also $\displaystyle x_{n+2}=\frac{n+1}{n+2}x_n$ : we can conclude that:

$\displaystyle 1\le \frac{x_{2C}}{x_{2C+1}}=$ $\displaystyle \frac{\pi}{2}(2C+1)\left(\frac{(2C-1)!!}{(2C)!!}\right)^2$ $\displaystyle =\binom{2C}{C}^2 \frac{\pi (2C+1)}{2^{4C+1}}$ , that implies $\displaystyle \binom{2C}{C}\ge \left(\frac{2^{4C+1}}{\pi (2C+1)}\right)^{\frac{1}{2}}$ . So, for the proof of our problem, it is enough that $\displaystyle \left(\frac{2^{4C+1}}{\pi (2C+1)}\right)^{\frac{1}{2}} \ge \frac{2^{2C+1}}{C+1}$ , that is $\displaystyle (C+1)^2\ge 2\pi (2C+1)$ ; using the weak inequalities $2C+1<2C+2$ and $\pi<3,15$ , it is enough that $(C+1)^2\ge 4\cdot 3,15\cdot (C+1)$ , that is $C\ge 4\cdot 3,15-1=11,6$ . The proof is complete since we assumed $C\in \mathbb{Z}\cap [12,+\infty)$ . []

Problem 17- A sum of prime powers is not a power of 2

Find all $(x,y,z)\in \mathbb{N}$ such that $5^x+7^y=2^z$ ,where $\mathbb{N}:=\{0,1,2,\cdots\}$ .

Solution. We will prove that if $(x,y,z)$ is a solution that $(x,y,z)\in S:=\{(0,0,1), (0,1,3), (2,1,5)\}$ .

1. If $x=y=0$ then $z=1$ , so that $(0,0,1) \in S$ .

2.If $x=0$ and $y\ge 1$ then $7^y+1=2^z$ . If $2\mid y$ then in $\mathbb{Z}/4\mathbb{Z}$ we have $2^z=(-1)^y+1=2$ , so that $y=1$ , but $2=7^y+1\ge 7^1+1$ is absurd. Otherwise, $2\nmid y$ , and in $\mathbb{Z}/16\mathbb{Z}$ we have $2^z=7^y+1=7\cdot 49^{\frac{y-1}{2}}+1=7+1$ : this is enough to find the other trivial solution $(0,1,3)\in S$ .

3. If $x\ge 1$ and $y=0$ then $5^x+1=2^z$ . Since $5^x+1\ge 6$ we have that $z\ge 2$ , and taking $\mathbb{Z}/4\mathbb{Z}$ we obtain $0=2^z=5^x+1=2$ , absurd.

4. From now, we can suppose $\min\{x,y\}\ge 1$ , so that $2^z=5^x+7^y\ge 5+7=12$ implies that $z\ge 4$ .

5. In $\mathbb{Z}/3\mathbb{Z}$ we have that $(-1)^z=2^z=5^x+7^y=(-1)^x+1$ , so $2\mid x$ and $2\nmid z$ .

6. In $\mathbb{Z}/4\mathbb{Z}$ we have that $0=2^z=5^x+7^y=1+(-1)^y$ , so $2\nmid y$ .

7. In $\mathbb{Z}/16\mathbb{Z}$ we have that $0=2^z=5^x+7^y=25^{\frac{x}{2}}+7\cdot 49^{\frac{y-1}{2}}=$ $9^{\frac{x}{2}}+7=3^x+7$ but residues of $3^i$ are exactly $[3,9,11,1]$ , so that we can conclude that $4\mid x-2$ .

8. To sum up all observations in points 5,6,7 , we can reformulate the problem as “find all $(a,b,c)\in \mathbb{N}^3$ such that $5^{4a+2}+7^{2b+1}=2^{2c+1}$ for some $c\ge 2$ .

9. In $\mathbb{Z}/25\mathbb{Z}$ we have that $0=5^{4a+2}=2^{2c+1}-7^{2b+1}=2^{2c+1}-7\cdot (-1)^b$ ; and since $\text{gcd}(13,25)=1$ then also $0=13(2^{2c+1}-7\cdot (-1)^b)=4^c-16\cdot (-1)^b$ . Now residues of $4^i$ are exacty $[4,16,14,6,24;21,9,11,19,1]$ , and we are searching $16\cdot (-1)^b \in \{9,16\}$ , that is equivalent to $5\mid c-2$ .

10. To sum up all observations in points 8,9 , we can reformulate the problem as “find all $(a,b,d)\in \mathbb{N}^3$ such that $5^{4a+2}+7^{2b+1}=2^{5(2d+1)}$ . We divide the rest of the solution in two cases:

PART 1.

11. Let’s find all solutions in the case $b=0$ , that is $5^{4a+2}+7=2^{10d+5}$ in non-negative integers.

12. The equation in point 11 is equivalent to $5^2\cdot (5^{4a}-1)=2^5\cdot (2^{10d}-1)$ , and we can see the trivial solution with $a=d=0$ that is $(x,y,z)=(2,1,5) \in S$ . Let’s show that no other integer solutions exist.

13. Consider the 2-adic valuations: it is true that $5=\upsilon_2(2^5(2^{10d}-1))=\upsilon_2(5^2(5^{4a}-1))=$ $\upsilon_2(5^{4a}-1)$ . And by the lifting lemma it is equal to $\upsilon_2(\frac{5^2-1}{2})+\upsilon_2(4a)$ , that implies $5=3+\upsilon_2(4a)$ , so $2||a$ .

14. Consider the equation in $\mathbb{Z}/13\mathbb{Z}$ (after observing that $13\mid 5^4-1$ ), and we obtain: $6\cdot 10^d=2^5\cdot 2^{10d}=5^2\cdot 5^{4a}+7=5^2+7=6$ that is equivalent to $6=\text{ord}_{13}(10)\mid d$

15. To sum up points 13,14, the equation becomes equivalent to $5^2\cdot (5^{2^3\cdot (2h-1)}-1)=2^5(2^{2^2\cdot 3\cdot 5k}-1)$ for some $h,k$ positive integers.

16. After observing that $17\mid \text{gcd}(5^8+1,2^4+1)$ (that is equivalent to $\text{ord}_{17}(5)=2\text{ord}_{17}(2)=16$ ), consider the equation of point 15 in $\mathbb{Z}/17\mathbb{Z}$ : we have that $5^2(5^{2^3\cdot (2h-1)}-1)=5^2((-1)^{2h-1}-1)=-2\cdot 5^2=1$ and $2^5(2^{2^2\cdot 3\cdot 5k}-1)=15((-1)^k-1) \in \{0,4\}$ . This is a contradiction.

PART 2.

17. Now let’s show that in the case $b\ge 1$ , the equation $5^{4a+2}+7^{2b+1}=2^{10d+5}$ has no solutions.

18. In $\mathbb{Z}/49\mathbb{Z}$ (the information in this point makes the difference from the previous part) we have $37^a=50\cdot 37^a=2\cdot(5^2\cdot 5^{4a})=2(5^{4a+2}+7^{2b+1})$ $=2(2^{10d+5})=64\cdot 2^{10d}=15\cdot 44^d=37^{18+16d}$ . Now, since $\text{ord}_{49}(37)=21$ , we conclude that $21\mid (18+16d)-a$ , that is equivalent to $3\mid a-d$ and $7\mid (2d+4)-a$ .

19. Observe that $7^6-1=2^4\cdot 3^2\cdot 19\cdot 43$ and take the equation in $\mathbb{Z}/9\mathbb{Z}$ , we have: $4^a+4^b=4\cdot (7\cdot 4^a+7\cdot 4^b)=4\cdot (25\cdot 5^{4a}+7\cdot 49^b)$ $=4\cdot (2^5\cdot 2^{10d})=2^7\cdot 2^{10d}=2\cdot 4^{2d}$ . We can see directly by hand that residues of $4^i$ are exactly $[4,7,1]$ and residues of $2\cdot 4^{2i}$ are $[5,8,2]$ . And we can see that $(a,b,d)$ is a solution if and only if $3\mid a+b-d$ .

20. Since we know that $3\mid a-d$ for point 18, then it is also true that $3\mid (a+b-d)-(a-d)=b$ . In particular if $d$ is a divisor of $7^6-1$ then $7^{2b+1}$ is constant in $\mathbb{Z}/d\mathbb{Z}$ .

21. In $\mathbb{Z}/43\mathbb{Z}$ we have $25\cdot 23^a+7=5^{4a+2}+7^{2b+1}=2^{10d+5}=32\cdot 35^d$ . Now $\text{ord}_{43}(23)=21$ and $\text{ord}_{43}(35)=7$ : complete residues of LHS are $[23,31,0,18,2,21,28; 17,22,8,30,20,5,4; 24,11,13,16,42,38,32]$ , and complete residues of RHS are $[2,27,42,8,22,39,32]$ .

22. Looking previous residues we can see that if $(a,d)$ is a solution modulo $7$ ( we can say that because $7=\text{ord}_{43}(35)\mid \text{ord}_{43}(23)\mid \varphi(43)$ ) then $(a,d)\in\{(5,1),(5,3),(3,4),(2,5),(7,7)\}$ .

23. In noone of previous couples $(a,d)$ modulo $7$ we verify that $7\mid (2d+4)-a$ , as requested in point 18. This is a contradiction. []

Problem 18. A equation on 4 non negative integers.

Solve the equation $p^nq^m=(p+q)^2+1$ in nonnegative integers.

Solution. Since the equation is simmetric in $p,q$ , we can assume without loss of generality that $0\le p\le q$ .

Moreover, we must have $\min\{n.m\}\ge 1$ : in fact, if $nm=0$ then there exists a integer $x\in \mathbb{Z}$ such that $x^2+1$ is a perfect non-trivial power. And it’s well known (working in $\mathbb{Z}[i]$ ) that the unique solution is $x=0$ , that is $p=q=0$ , but $(p,q,n,m)=(0,0,0,m)$ or $(0,0,n,0)$ do not work.

If $p=0$ then $0=q^2+1\ge 1$ , that is a contradiction. And, if $d:=\text{gcd}(p,q)$ then $d\mid p^nq^m=(p+q)^2+1 = d^2 \left(\frac{p+q}{d}\right)^2+1$ that implies $d\mid 1$ , so if $(p,q,n,m)$ is a solution then $p$ and $q$ are coprime positive integers.

Also, looking the equation in $\mathbb{Z}/p\mathbb{Z}$ and $\mathbb{Z}/q\mathbb{Z}$ we deduce also that $p\mid q^2+1$ and $q\mid p^2+1$ .

If $p=1$ then $q^m=(q+1)^2+1$ and, as before, $x^2+1$ is never a non trivial perfect power.

If $p=2$ then, since $q\mid p^2+1=5$ , we have to verify if $(2+5)^2+1=2^n5^m$ , and we have the solutions $(p,q,n,m)=(2,5,1,2)$ (and the simmetrical $(p,q,n,m)=(5,2,2,1)$ ).

If $p=3$ then, since $q\mid 3^2+1$ , we have to verify only two cases: $3^n5^m=8^2+1$ and $3^n10^m=13^2+1$ , and both have no solutions. From now, we can assume $p\ge 4$ .

Since $q\mid p^2+1$ then we can examine first cases (when $q$ is “big”): if $q=(p^2+1)\frac{1}{i}$ for some $i\in \{1,2,3\}$ then $p\mid q^2+1= \frac{p^4+2p^2+1}{i}^2+1 \equiv \frac{i^2+1}{i^2}\pmod{p}$ (this congruence is $i\mid p^2+1$ implies $\text{gcd}(p,i)=1$ , so there exist $j$ such that $\text{gcd}(p,j)=1$ and $p\mid ij-1$ ). It means that $p\mid i^2+1$ :

- if $i=1$ then $p\mid 1^2+1=2$ , but we already examined this case;

- if $i=2$ then $p\mid 2^2+1=5$ , and $q=\frac{1}{2}(p^2+1)=13$ . But $5^n13^m=18^2+1=5^2\cdot 13$ and we have the solution $(p,q,n,m)=(5,13,2,1)$ and its simmetrical one.

- if $i=3$ then $p\mid 3^2+1=10$ , and since $p\ge 4$ we have to check only cases $p\in \{5,10\}$ . But in both cases $q=\frac{1}{3}(p^2+1)$ is not a integer, since $-1$ is not a quadratic residue in $\mathbb{Z}/3\mathbb{Z}$ . From now, we can assume that if $q=\frac{p^2+1}{i}$ then $i\ge 4$ : it means that $p^2\ge 4q-1$ .

To sum, other than two previous solutions, if $(p,q,n,m)$ verify the original equation, then $\max\{\sqrt{4q-1},4\}\le p\le q-1$ and $\text{gcd}(p,q)=1$ , and $\min\{n,m\}\ge 1$ .

If $n+m=2$ then $n=m=1$ and $pq=(p+q)^2+1$ if and only if $0=(2p+q)^2+3q^2+4\ge 4$ , that is a contradiction.

If $n+m=3$ then $n=1, m=2$ (that is $pq^2=(p+q)^2+1\le (2q-1)^2+1<4q^2$ implies $p<4$ ), or $n=2, m=1$ (that is $(2q-1)^2+1\ge (p+q)^2+1=p^2q\ge q(4q-1)$ , contradiction).

If $n+m:=t\ge 4$ then $(2q-1)^2+1\ge (p+q)^2+1=p^nq^m\ge p^{t-1}q\ge$ $p^3q> p^2q\ge q(4q-1)$ , that is a contradiction.

We proved that if $(p,q,n,m)$ is a solution (with $p\le q$ ) then it belongs in $\{(2,5,1,2),(5,13,2,1)\}$ . []

Problem 19. Simmetric divisibilty

Find all $(a,b)\in \mathbb{N}_0^2$ such that $a^2b^2+ab^2+1\mid a^4+a^3+1$ .

Solution. It’s clear that $a=b$ is a infinite class of solutions and that otherwise we must have $1\le b\le a-1$ . It holds also $a^2b^2+ab^2+1\mid a^4+a^3-1-(a^2b^2+ab^2+1)=a(a+1)(a^2-b^2)$ . Since $\text{gcd}(a^2b^2+ab^2+1,a(a+1))=1$ then it holds also : $\displaystyle a^2b^2+ab^2+1$ divides $a^2-b^2$ . But $a^2-b^2<a^2<a^2b^2+ab^2+1$ , that’s a contradiction. []

Problem 20. Even implies divisible by 8

If $a,b\in \mathbb{N}_0^2$ are fixed such that $\displaystyle \frac{(2a)^{b+1}-1}{2a-1}$ is a perfect square, then $a$ is idivisible by $4$ .

Solution. Define the integer $A:=2a$ , then $1+A+A^2+\ldots+A^b$ is a perfect square. Since $A$ is even, then $8\mid A^i$ for all $i\ge 3$ . If $A\equiv 2,4,6$ in $\mathbb{Z}/8\mathbb{Z}$ then $1+A+A^2+\ldots+A^b\equiv 1+A+A^2 \not \equiv 1$ . Otherwise $8\mid A$ , that’s our aim. []

Problem 21. Sum of powers of 2 is a fixed integer

Find all non negative integers $x,y,z$ such that $2^x+2^y+2^z=2336$ .

Solution. It’s well-known that every positive integer has a unique binary representation. If $m$ is a fixed positive integer, then define $f(m)$ the number of 1 that are in his binary representation. Since $2336=2^{11}+2^8+2^5$ then $f(2336)=3$ . Now, if $x=y=z$ then $2^x+2^y+2^z=3\cdot 2^x=2^{x+1}+2^x$ and it means that $f(3\cdot 2^x)=2$ . Instead, if $x=y$ and $z\neq x$ then $2^x+2^y+2^z=2^{x+1}+2^z$ : it means that $f(2^{x+1}+2^z)=2$ if $z\neq x+1$ or $1$ if $z=x+1$ . In all previous cases $3=f(2336)=f(2^x+2^y+2^z)\le 2$ . It means that if a triple solution $(x,y,z)\in \mathbb{N}^3$ exists then wlog $0\le x<y<z$ . But since the binary representation is unique, then we must have $(x,y,z)=(5,8,11)$ and all his $3!$ permutations. []

Problem 22. Divisibility again

Define $m:=2007^{2008}$ . How many positive integers $n<m$ satisfy $m\mid n(2n+1)(5n+2)$ ?

Solution. Since $\text{gcd}(n,2n+1)=\text{gcd}(2n+1, 5n+2)=1$ and $\text{gcd}(n,5n+2)$ is $1$ or $2$ (but in all cases coprime with $2007=3^2\cdot 223$ ), then by chinese remainder theorem we’ll have exactly a solution in the interval $[1,2007^{2008}]$ to the system of congruences: $3^{4016}\mid p_i(n), 223^{2008}\mid p_j(n)$ , where $1\le i<j\le 3$ and $p_1(n):=n, p_2(n):=2n+1, p_3(n):=5n+2$ . The number of way to choose $p_i(n)$ and $p_j(n)$ is evidently $2\binom{3}{2}=6$ , and noone solution of them is exactly $2007^{2008}$ . Otherwise we have the cases in which $m\mid p_i(n)$ for some $1\le i\le 3$ , but we have to exclude the case $i=1$ that leads to the solution $n=m$ . So, we can conclude that there are exactly $8$ distinct positive integers $n<m$ such that $m\mid p_1(n)p_2(n)p_3(n)$ . []

Problem 23. A Easy equation in positive integers

Find all $(x,y)\in \mathbb{N}_0^2$ such that $x^3-y^3=2xy+8$ .

Solution. Since $2xy+8>0$ then it implies that $x>y>0$ , and since $2\mid 2xy+8$ then also $2\mid x^3-y^3$ , that’s $2\mid x-y$ . Now the following inequality holds: $xy+4=\frac{2xy+8}{2}=\frac{x-y}{2}(x^2+y^2+xy)\ge x^2+y^2+xy$ , that’s equivalent to $x^2+y^2\le 4$ : it means that $x=3, y=1$ , but also this couple does not satisfy the original equation, so there are no solutions. []

Probem 24. Exponential equation with integers

Find all $(a,b)\in \mathbb{Z}^2$ such that $a^{2^b}-b^{2^a}=2$ .

Solution. We’ll show that if $(a,b)$ is a solution then $(a,b)\in\{(0,-2),(2,0),(9,-1)\}$ .

- If $a=0$ then $-b^1=2$ .

- If $b=0$ then $a^1=2$ .

- If $a>0, b<0$ then $a^{2^b}$ is a integer, since it’s difference of two integers. It means that a positive integer $A$ exists such that $a=A^{2^{|b|}}$ . The equation becomes $A-(-|b|)^{2^{A^{2^{|b|}}}}=2$ , that’s $|b|^{2^{A^{2^{|b|}}}}=A-2$ . If $|b|=1$ then $b=-1$ , and $A=3$ , implying that $a=A^{2^{|b|}}=9$ . Otherwise $|b|\ge 2$ : then $\displaystyle |b|^{2^{A^{2^{|b|}}}}$ $>2^{2^A}\ge 2^A+1>A-2$ .

- If $a<0, b>0$ , then $b^{2^a}$ is a integer, since it’s difference of two integers. It means that a positive integers $B$ exists such that $b=B^{2^{|a|}}$ . The equation becomes $|a|^{2^{B^{2^{|a|}}}}=B+2$ . Since $B>0$ then $|a|^{2^{B^{2^{|a|}}}}=B+2>2$ implies that $|a|\ge 2$ . The following chain of inequalities holds: $|a|^{2^b}\ge 2^{2^b}\ge 2^{b+1}=$ $2\cdot 2^b\ge 2(b+1)=$ $2(B^{2^{|a|}}+1)\ge 2B^4+2>B+2$ , that’s a contradiction.

- If $a<0, b<0$ we have no solution since the equation becomes $(-|a|)^{2^{-|b|}}-(-|b|)^{2^{-|a|}}=2$ and $(-1)^{2^{-x}}$ is not defined in $\mathbb{R}$ for all integer $x>0$ .

- If $a>0, b>0$ , then define the positive integers $x:=a^{2^{b-1}}, y:=b^{2^{a-1}}$ ; the equation becomes $(x+y)(x-y)=2$ and it implies $x+y=2$ and $x-y=1$ . This system has no solution in positive integers $x,y$ . []

Comments (2)

04/11/2009

f(n)<f(n+1)<f(n+2) for infinitely many n

Filed under: Mathematical matters — bboyjordan @ 7:35 PM

We’ll show in this post that for some $f(\cdot):\mathbb{N}\setminus\{0,1\}\to S$ fixed function, where $S \subseteq \mathbb{R}$ and $|S| \ge 3$ , there exist infinitely many $n\in \mathbb{N} \setminus \{0,1\}$ such that $f(n)<f(n+1)<f(n+2)$ .

Proposition 1. The statement is true if $f(\cdot):=\omega(\cdot)$ . (TST Germany 2006)

Solution. We’ll show that it is true for infinitely many values of $x_n$ , where $x_n:=2^n$ . We can note that if $y_n:=\text{gpf}(n) \in \mathbb{P}$ then $1<2^{y_n}+1 \mid x_n+1$ . At the same way if $z_n:=\text{lpf}(n) \in \mathbb{P}$ then $1<2^{z_n}+1 \mid x_n+1$ . Assume that $z_n >2$ , then $2 \nmid y_nz_n$ and $\text{gcd}(2^{y_n}+1,2^{z_n}+1)=2^{\text{gcd}(y_n,z_n)}+1 \text{ }\vdots \text{ }3$ : so if $\Lambda(2^n+1)>0$ (where $\Lambda(\cdot)$ is the Mangoldt function) then $2^n+1=3^m$ for some $m \in \mathbb{N}_0$ ; but it has only finitely many solutions, since by the Lifting Lemma $m=\upsilon_3(3^m)=\upsilon_3(2^n+1)=\upsilon_3(n)+1$ , so $2^n<2^n+1=3^m<4^{1+\upsilon_3(n)}<2^{2+2\ln(n)}$ , that is false definitively.It means that $z_n=2$ , so $x_n$ is a square. Assuming that $\omega(x_n) \le \omega(x_n+1)$ by contradiction, we should have $\Lambda(x_n+1)=0$ . But we can easily show a more general fact: $x^2+1$ is never a non-trivial power of some positive integers. In fact, if $x^2+1=y^n$ for some positive integer $y,n$ , then $x$ is even (otherwise modulo $4$ we should have $n\mid 1=\upsilon_2(x^2+1)$ ). But working in the extension $\mathbb{Z}[i]$ we have $\text{gcd}(x+i,x-i)=1$ , so they are both $n$ -power. So it must exist $(a,b) \in \mathbb{Z}^2$ such that $(a+bi)^n=x+i$ , but seeing the $i$ -coefficient we must have $(a,b)=(0,-1)$ , from which the unique trivial solution $(x,y)=(0,1)$ follows. It means that $y_n=z_n=2$ : in other words, if $\Lambda(x_n+1)>0$ then $n$ is a power of $2$ .

By proving the original statement, it is enough to assume that it holds for only finitely many values of $n$ , and we’ll obtain a contradiction. So, in particular, assume that if $t \in \mathbb{N}_0$ is not a power of $2$ then $\omega(2^t+1) \ge \omega(2^t+2)=1+\omega(2^{t-1}+1)$ definitively. It means that if $h \in \mathbb{N}_0$ is enough large to avoid all finitely many solutions of above cases then $\omega(2^{2^{h+1}-1}+1)>\omega(2^{2^{h+1}-2}+1)>\omega(2^{2^{h+1}-3}+1)>\ldots>\omega(2^{2^h+1}+1)>1$ , that is $\omega(2^{2^{h+1}-1}+1) \ge 2^h$ definitively. And it implies that $2^{2^{h+1}}>2^{2^{h+1}-1}+1\ge p_{2^h}\#$ , where $\displaystyle p_i\#:=\prod_{1 \le j \le i}{p_j}$ and $p_j$ is the $j$ -th prime of $\mathbb{P}$ . Taking the natural logaritm, it is true that $\displaystyle \theta(p_{2^h}):=\sum_{1 \le i \le 2^h}{\ln(p_i)}<2^{h+1}$ (where $\theta(\cdot)$ is a Chebychev function). But the Prime Number Theorem is equivalent to $\theta(x) \sim x$ , so we have that $2^{h+1}$ is asymptotically greater than $p_{2^h}$ . And PNT is again equivalent to $p_n \sim n\ln(n)$ , so we should have that $2^{h+1}$ is definitively greater than $\ell h2^h$ , where $\ell$ represents a positive fixed constant. And it is clearly false. []

Proposition 2. The statement is true if $f(\cdot):=\text{gpf}(\cdot)$ . (Brazilian Olympiad 1995 and Bulgaria 1995)

Solution. It is enough to fix $n=p-1$ for some $p \in \mathbb{P}\setminus\{2\}$ .

Infact $f(n) \le \frac{p-1}{2} < p=f(n+1)$ , and assume that $f(n+2)<f(n+1)$ :it means that $f(p^2-1)<f(p^2)=p$ . Assume again that $f(p^2+1)>f(p^2)$ then we’ll have, after continuing this algorithm infinitely many times, $f(p^{2^k}+1)>f(p^{2^k})=p$ for all $k \in \mathbb{N}$ . Note that $p^{2^k}+1$ cannot be definitively a power of $2$ since it is in the form $y^2+1$ (see proposition 1). So, if $q\mid p^{2^k}+1$ for some $q \in \mathbb{P}\setminus\{2\}$ then $2^{k+1}=\text{ord}_q(p) \mid \varphi(q)=q-1$ , so $q>2^k$ definitively, that is clearly a contradiction. []

Proposition 3. The statement is true if $f(\cdot):=\varphi(\cdot)$ . (Unknown source)

(Under construction)

Comments (4)

A list of own problems

Filed under: Own Problems — bboyjordan @ 5:38 PM

Problem 1 Define the sequence of $\{x_i\}_{i \in \mathbb{N}_0}$ such that $x_i = i$ for $i \in \{1,2,3\}$ and $\displaystyle x_{n + 3} = \frac {x_{n + 2}^{5} + x_n^2}{ x_{n + 1}^{ 3}}$ for all $n \in \mathbb{N}_0$ . Find all $m \in \mathbb{N}_0$ such that the equation $\displaystyle x_m = \frac{a^{3} + b^{7}}{c^{13}+d^{17}}$ has no solutions in $(a,b,c,d) \in \mathbb{Z}^4$ .

Problem 2 Let $X: = \{x_1,x_2,\ldots,x_{29}\}$ be a set of $29$ boys: they play with each other in a tournament of Pro Evolution Soccer 2009, in respect of the following rules:
i) every boy play one and only one time against each other boy (so we can assume that every match has the form $(x_i \text{ Vs } x_j)$ for some $i \neq j$ );
ii) if the match $(x_i \text{ Vs } x_j)$ , with $i \neq j$ , ends with the win of the boy $x_i$ , then $x_i$ gains $1$ point, and $x_j$ doesn’t gain any point;
iii) if the match $(x_i \text{ Vs } x_j)$ , with $i \neq j$ , ends with the parity of the two boys, then $\frac {1}{2}$ point is assigned to both boys.
(We assume for simplicity that in the imaginary match $(x_i \text{ Vs } x_i)$ the boy $x_i$ doesn’t gain any point).
Show that for some positive integer $k \le 29$ there exist a set of boys $\{x_{t_1},x_{t_2},\ldots,x_{t_k}\} \subseteq X$ such that, for all choice of the positive integer $i \le 29$ , the boy $x_i$ gains always a integer number of points in the total of the matches $\{(x_i \text{ Vs } x_{t_1}),(x_i \text{ Vs } x_{t_2}),\ldots, (x_i \text{ Vs } x_{t_k})\}$ .

Problem 3 Define $\displaystyle \Phi_n(x):=\sum_{i=0}^{n-1}{x^i}$ for all $n \in \mathbb{N}_0$ , where $\mathbb{N}_0:=\mathbb{N} \setminus \{0\}$ .
Let $a \in \mathbb{N} \setminus \{0,1\}$ fixed; show that exist infinitely many $n \in \mathbb{N}_0$ such that $\displaystyle \text{gpf}(\Phi_n(a))>n\log_a{n}$ .

Problem 4 Let $\{\sigma(1), \sigma(3), \sigma(5),..., \sigma(2009)\}$ be a permutation of $\{1,3,5,\ldots,2009\}$ .
If we know that $\displaystyle P(x)=\sum_{i=0}^{1004}{(-1)^i\sigma(2i+1)x^{2i}}$ is not monic, show that if exist $\alpha \in \mathbb{R}$ such that $P(\alpha)=0$ then $\alpha+29>0$ .

Problem 5 Let $a \in \mathbb{N} \setminus \{0,1\} \text{ and } b \in \mathbb{N}_0$ fixed. Show that exist infinitely many $n \in \mathbb{N}_0$ such that $\displaystyle \log_a{(\text{gpf}^b(\Phi_n(a)))}<n$ .

Problem 6. Let $\{L_i\}_{i \in \mathbb{N}}$ be the Lucas sequence defined by $L_0=L_1+1=2 \text{ and } L_{n+2}=L_n+L_{n+1}$ for all $n \in \mathbb{N}$ . Show that every odd divisor of $L_{2n}$ has a even tens digit. (by Gebegb)

Problem 7. Let $n \in \mathbb{N}_0$ fixed, and define $s(n): = \{x \in \mathbb{Z}: 1 \le x \le n \text{ and } x \mid 2^x + 1\}$ , and let a real $k > 0$ fixed. Show that $2\ln(n) < |s(n)| < kn$ holds definitively.

Solution. We can begin noting that the infinite sequence of positive integers $\{x_i\}_{i \in \mathbb{N}}$ defined by $x_0:=1,x_{n+1}:=2^{x_n}+1$ for all $n \in \mathbb{N}$ verify the divisibility relation $x_n \mid 2^{x_n}+1$ . Easily by PMI, if $x_i \mid 2^{x_i}+1$ for all $i<n$ , then $\displaystyle 2^{x_n}+1=2^{2^{x_{n-1}}+1}+1=\left(2^{\frac{2^{x_{n-1}}+1}{x_{n-1}}}\right)^{x_{n-1}}+1 \text{ } \vdots \text{ } 2^{x_{n-1}}+1=x_n$ . On the other hand it is also true that the infinite sequence of positive integer $\{y_i\}_{i \in \mathbb{N}}$ defined by $y_i:=3^i$ verify the divisibility relation too, infact $1=y_0 \mid 2^{y_0}+1$ , and again by PMI, if $y_i \mid 2^{y_i}+1$ for all $i<n$ then $\displaystyle y_n=3y_{n-1} \mid 2^{3y_{n-1}}+1=\left(2^{y_{n-1}}+1\right)\phi_3(-2^{y_{n-1}})$ . So it is enough to show that $\displaystyle 2^{2 \cdot 3^{n-1}}-2^{3^{n-1}}+1 \text{ }\vdots \text{ }3$ , that is true since in $\mathbb{F}_3$ we have $4^{3^{n-1}}-2^{3^{n-1}}+1=1-(-1)+1=0$ .

We can show now that only the sequences $\{x_i\}_{i \in \mathbb{N}}$ and $\{y_i\}_{i \in \mathbb{N}}$ have only a finite number of common elements: in fact if $x_a=y_b$ for some $(a,b) \in \mathbb{N}^2$ then $2^{x_{a-1}}+1=3^b$ , but it is well known the equation $2^x+1=3^y$ has only finitely many solution in $\mathbb{N}$ , since by the Lifting Lemma $y=\upsilon_3(3^y)=\upsilon_3(2^x+1)=\upsilon_3(x)+1$ , but $2^x<2^x+1=3^y<4^{1+\upsilon_3(x)}<2^{2+2\ln(x)}$ , that is false definitively (it can be seen also as a corollary of Mihailescu Theorem).

Obviusly both sequences are strictly increasing, so it is true that each sequences have at least respectively $\lfloor \text{log}_{2,1}(n) \rfloor$ and $\lfloor \text{log}_3(n) \rfloor$ elements that are not greater than $n$ , so $|s(n)|> \lfloor \text{log}_{2,1}(n) \rfloor+\lfloor \text{log}_3(n) \rfloor > 2 \ln(n)$ definitively.

About the upper bound, it is equivalent to show that $\displaystyle \lim_{n \to +\infty}{\frac{|s(n)|}{n}}=0$ .

Note that $p \mid 2^{pk}-2^k$ for all $(p,k) \in \mathbb{P} \times \mathbb{N}$ , so that $\text{ord}_p(2)=\text{ord}_p(2^p)$ . Now if $p \mid 2^t \pm1$ then $2^t \ge p \mp 1 \ge 2^{\ln(p)}$ for all $p \in \mathbb{P}$ sufficiently large. It means that $\text{ord}_p(2) \ge \ln(p)$ , and also that if $p \mid x \in s(n)$ then $x \ge \ln(p)$ . So, in the set $s(n)$ there are at most $\displaystyle n\left(p\ln(p)\right)^{-1}$ numbers multiple of $p$ .

Let $q \in \mathbb{P}$ fixed and define $\displaystyle r_q(n):=\{x \in \mathbb{N}: 1\le x \le n \text{ and gpf}(x)<q\}$ . Clearly we have that $\displaystyle \ell\left(\ln(n)\right)^q < | r_q(n) |$ for some positive real $\ell$ fixed.

It is enough to conclude since $\displaystyle \lim_{n \to +\infty}{\frac{|s(n)|}{n}} \le \lim_{n \to +\infty}{\frac{|r_q(n)|+\sum_{q \le p \in \mathbb{P}}{n\left(p\ln(p)\right)^{-1}}}{n}}$ $\displaystyle \le \lim_{n \to +\infty}{\ell \frac{\left( \ln(n) \right)^q}{n}}+\lim_{n \to +\infty}{\sum_{q \le p \in \mathbb{P}}{\left(p\ln(p)\right)^{-1}}}$ , but if $q \in \mathbb{P}$ is sufficiently large, then both limits can be arbitrary small. []

Problem 8. Let a convex quadrilateral $ABCD$ fixed such that $AB = BC$ , $\angle ABC = 80, \angle CDA = 50$ . Define $E$ the midpoint of $AC$ ; show that $\angle CDE = \angle BDA$

Solution . X in BE such that CXE=CDE so DECX cyclic so DXE=DCE=180-CDA-CAD=180-CAB-CAD=180-BAD, so ABXD cyclic so BDA=AXB=CXE=CDE.

Problem 9. Find all $(x,y,z) \in \mathbb{Z}^3$ such that $x^3 - 5x = 1728^{y}\cdot 1733^z - 17$ .

Solution. 2 doesn’t divide f(x):= x³ – 5x + 17 that is integer, so min{y,z}>-1 and y = 0. If $z = 0$ there are no solutions, so $f(x) \ge 1733 \implies x > 10$ Now $f(x) \in \{0,1,3,5,6\}$ in $\mathbb{F}_7$ so we have the only case $3 \mid z$ . So $f(x)$ must be a cube, but $(x - 1)^3 < f(x) < x^3$ for all $x > 10$ .

Problem 10. Define the function $g(\cdot): \mathbb{Z} \to \{0,1\}$ such that $g(n) = 0$ if $n < 0$ , and $g(n) = 1$ otherwise. Define the function $f(\cdot): \mathbb{Z} \to \mathbb{Z}$ such that $f(n) = n - 1024g(n - 1024)$ for all $n \in \mathbb{Z}$ . Define also the sequence of integers $\{a_i\}_{i \in \mathbb{N}}$ such that $a_0 = 1$ e $a_{n + 1} = 2f(a_n) + \ell$ , where $\ell = 0$ if $\displaystyle \prod_{i = 0}^n{\left(2f(a_n) + 1 - a_i\right)} = 0$ , and $\ell = 1$ otherwise. How many distinct elements are in the set $S: = \{a_0,a_1,\ldots,a_{2009}\}$ ?

Solution. Consider the obvious bijection between {1,…,2048} and the strings of 11 binary digits. The problem states that we begin with $x_1: = 1$ , and that if $x_n = 0\ell$ or $x_n = 1\ell$ (where $\ell$ is a string of 10 binary digits) then $x_{n + 1} = \ell 1$ if we can find i<n+1 such that $x_i = \ell$ , otherwise $x_{n + 1} = \ell 0$ . Define $k: = \max\{n \in \mathbb{N}: \prod_{1 \le a < b \le n}{(x_a - x_b)} \neq 0\}$ and $S: = \{x_1,...,x_k\}$ . Suppose that $x_k = ey$ for some e in {0,1} and a string y of 10 binary digits, then $x_{k + 1} = y0 \in S$ by definition of k, so define $x_i: = y0 \in S$ the other i such that 1<i<k+1. And, if $x_k = ey$ then define j that integer such that 0<j<k+1 and $x_j: = y1 \in S$ (it must exist since $x_{k + 1} = y0$ ). If j>1 then $\{x_{i - 1},x_{j - 1}\}$ exist and is $\{0y,1y\}$ , then $x_k \in \{x_{i - 1},x_{j - 1}\}$ , contradiction, so j=1. It means that $latex y=0 \in S$, and if $e = 1$ then $x_{k - 1} \in \{0,x_k\}$ , contradiction, so $x_k = 0$ . Clearly $1 \le k \le 2048$ ; suppose that $k < 2048$ . A number $a \in \{0,1\}$ and a string $b$ of 10 binary digits exist such that $ab \not \in S$ , and suppose $b0 \in S$ (clearly $b \neq 0$ ).Define $x_w: = b0 \in S$ for some 1<w<k+1, then there exist 0<z<k+1 such that $x_z = b1 \in S$. As before if z>1 then $\{x_{w - 1},x_{z - 1}\}$ exist and is $ab \in \{0b,1b\} \subseteq S$ , contradiction; and if z=1 then b=0, again contradiction. So a number $ab$ does not belong to S only if $b0 \not \in S$ . But in this way we can define a sequence of number that do not belong to S, and that is eventually null, but $a_k = 0$ .
It shows that $\prod_{0 \le i < j \le 2047}{(a_i - a_j)^2} > 0$ .[]

Problem 11. Let $a,b$ be two positive integer fixed such that $b>1$ . Evaluate $\min\{n \in \mathbb{N}_0: \lfloor \text{log}_b(n)+\text{log}_b(b^a+1) \rfloor - \lfloor \text{log}_b(n) \rfloor >a \}$ .

Solution. It is equivalent to search the minimum positive integer integer n such that $nb^{a+1}$ and $n(b^a+1)$ have the same number of digit in base $b \in \mathbb{N} \setminus \{0,1\}$ . Working in base $b$ , if $(x,y) \in \{0,1,2...,,b-1\}^2$ then $x+y<2b$ , so the max “report” when we compute $nb^a+n$ in the leftmost place is 1.And trivially $n$ need to have at least $a+1$ digits. So the minimum integer is $n=b^{a+1}-b+1$ .[]

Problem 12. (a) Let $a,b,c$ positive integer such that $a+b+c \mid a^2+b^2+c^2$ . Show that $a+b+c \mid a^n+b^n+c^n$ for infinitely many positive integer $n$ . (Laurentiu Panaitopol,TST Romania1987)

(b) Show that there exist infinitely many triple of positive integers $(a,b,c)$ such that $\text{gcd}(a,b,c)=1$ and $a+b+c \mid a^2+b^2+c^2$ and $a+b+c \nmid a^n+b^n+c^n$ for infinitely many positive integer $n$ . (Me)

Solution. (a) Since $a^n+b^n+c^n$ is a symmetric polynomial, it can be written in terms of $\sigma_1:=a+b+c$ , $\sigma_2:=ab+bc+ca$ and $\sigma_3:=abc$ (see the fundamental theorem of symmetric function). Now since $\sigma_1 \mid \sigma_2$ by assumption, if $a^n+b^n+c^n$ is made only by monomial of the form $\sigma_3$ , then it has a degree multiple of 3. But $|\mathbb{N} \setminus 3\mathbb{N}|=+\infty$ .

(b) There exist infinitely many primes $p \in \mathbb{P}$ such that $6 \mid p-1$ (in fact, if this set is finite and P is the product of its elements, then $4P^2+3$ should have only prime divisor of the form $6k-1$ but it is false since $\left(\frac{-3}{q}\right)=-1$ for all prime $q$ such that $6 \mid q+1$ ; in all way, it is a corollary of Dirichlet theorem). Set $b:=1$ and $c:=p-(a+1)$ then $p \mid a^2+1+(a+1)^2$ ; it means that if $p>2$ and $6 \mid p-1$ then $p \mid (2a+1)^2+3$ for some integer $a \in \mathbb{Z} \cap [1,p-2]$ (in fact $2a+1$ takes a complete residue system in $\{0,1,\ldots,p-1\}$ and $a \in \{p-1,0\}$ does not work). Define $a_0$ this integer, so $a_0+1+(p-a_0-1)=p \mid a_0^2+1^2+(p-a_0-1)^2$ and $p \nmid a_0^n+1^n+(p-a_0-1)^n$ for infinitely many positive integer $n$ . This is true, since it is enough to take $n=k \frac{p-1}{2}$ and by Euler criterion we have $a_0^n+1^n+(p-a_0-1)^n=\left(\frac{a_0}{p}\right)^k+1+\left(\frac{p-a_0-1}{p}\right)^k$ in $\mathbb{Z}/p\mathbb{Z}$ . But a sum of odd number of odd addends is odd, and in particulat it is non null.[]

Problema 13. Fix a strictly increasing sequence of $\{a_i\}_{i \in \mathbb{N}}\subseteq \mathbb{N}_0$ such that ten n-th terms is not bigger than nx+y definitively for some $(x,y) \in (\mathbb{R}^+)^2$ . Show that $\displaystyle \omega\left(\prod_{i \in \mathbb{N}}{a_i}\right)=+\infty$ .

Solution. By contradiction if $S$ is set of prime divisor of $\displaystyle \prod_{i \in \mathbb{N}}{a_i}$ and $|S|<+\infty$ then we’ll have that $\displaystyle \sum_{i \in \mathbb{N}}{\frac{1}{xi+y}}$ $\displaystyle \le \sum_{i \in \mathbb{N}}{\frac{1}{a_i}} \le \prod_{p \in S}{\left( \sum_{j \in \mathbb{N}}{\frac{1}{p^j} }\right)}$ definitively, that is clearly a contradiction. []

Problem 14. Prove that in the set $S :=\{2008,2009,...,4200\}$ there are $5^3$ elements such that any three of them are not in arithmetic progression.

Problem 15. Let $0<a_1<a_2<a_3<...<a_{10000}<20000$ be integers such that $\text{gcd}(a_i,a_j) < a_i, \forall i < j$ ; is $500 < a_1$ (always) true ?

Solution. It is enough to show that if we have $2n > 3^k$ distinct positive integers s.t. noone divides another one, so the smallest element is at least $2^k$ . Let $\upsilon_p(x)$ be the $p -$ adic valuation of $x$ , so naturally there exist a bijective function from $\{\frac {a_i}{\upsilon_2(a_i)}\}$ to $\{2i - 1\}$ , where $1 \le i \le 10^4$ . Consider the numbers s.t. $\upsilon_p(a_i) = 0, \forall p > 3$ : if $\upsilon_2(a_i) \le \upsilon_2(a_j)$ and $\upsilon_3(a_i) \le \upsilon_3(a_j)$ we have contradiction: it follows that $\upsilon_2(a_i) + \upsilon_3(a_i) \ge k$ , so the only number $a_h$ with $\frac {a_h}{2^{\upsilon_2(a_h)}} = 1$ has the property that $\upsilon_2(a_h) \ge k$ . Now it is enough to prove that $h = 1$ , but it is quite easy considering the number in the form $2^a3^bp$ and using similar tecnique as above.

Problem 16. Let $(a,b,c)\in \mathbb{N}_0^3$ fixed and let $p(\cdot),q(\cdot),r(\cdot)\in \mathbb{N}[x]$ be three polynomial such that $\min\{\text{deg}(p(\cdot)),\text{deg}(q(\cdot)),\text{deg}(r(\cdot))\}>0$ . Show that the equation $\displaystyle \pi^a(p(n)) = s^b(q(n)) + \sigma_0^c(r(n))$ has only a finite number of solutions, where $s(m)$ denotes the sum of digit of a positive integer $m$ .

Problem 17. Let $(a,b)\in \mathbb{Z}^2$ fixed such that $\min\{a,b\}\ge 2$ and fix also non constant polynomials $p_i(\cdot):\mathbb{R}\to\mathbb{R}$ for each $i\in\mathbb{Z}\cap[0,a+4]$ . Now define the function $f_4(\cdot):\mathbb{N}\to\mathbb{Z}\cap [0,4):x\to x-4\lfloor x\cdot 4^{ - 1}\rfloor$ and $g_b(\cdot):\mathbb{N}\to\mathbb{N}_0$ such that $g_b(x)=x^b$ if $b$ appears in the decimal representation of $x$ , otherwise $g_b(x) = b^x$ .
Show that it does not exist a non-zero polynomial $P[x_1,x_2,\ldots,x_{a + 5}]\in\mathbb{R}[x_1,x_2,\ldots,x_{a + 5}]$ such that for all $n\in\mathbb{N}_0$ the equation :
$\displaystyle P[p_0(\sigma_0(n)),p_1(\sigma_1(n)),$ $\displaystyle \ldots,p_a(\sigma_a(n)),p_{a + 1}(\omega(n)),p_{a + 2}(\varphi(n)),p_{a + 3}(f_4(n)),p_{a + 4}(g_c(n))] = 0$ holds.

Leave a Comment

31/10/2009

A list of funny problems

Filed under: Mathematical matters — bboyjordan @ 8:39 AM

Problem 1- Every number m,2m,…,nm has all digits

From Cono Sur Olympiad: “Show that for all $n \in \mathbb{N}_0$ there exist $m \in \mathbb{N}_0$ such that the number $im$ has all digits in the set $\{0,1,2,\ldots,9\}$ for all $i \in \mathbb{Z} \cap [1,n]$ “.

Solution. It is enough to set $\displaystyle m:=\sum_{1\le i \le 100}{i10^{in^2}}$ .

Let’s verify our claim. If $n=1$ then $10^{10} \mid m-9876543210$ , that clearly works. Otherwise, suppose that $n \in \mathbb{N} \setminus \{0,1\}$ . We have by construction that $10 \mid m$ for all choice of $n \in \mathbb{N}_0$ , so it is enough to concentrate our attention on the digits of the set $\{1,2,\ldots,9\}$ . Since in decimal representation, for all $x \in \mathbb{N}_0$ there are exactly $\lfloor \text{Log}(x) \rfloor +1$ digits (such that the first one is strictly positive) then it is easy to see that the number of digits of $i10^{in^2}$ is less than the number of digits of $10^{(i+1)n^2}$ for all $i \in \mathbb{Z} \cap [1,100)$ . In fact the inequality $\lfloor \text{Log}i10^{in^2} \rfloor +1< in^2+2 \le (i+1)n^2+1$ holds always. It means that it is enough to verify that the set of numbers $S:=\{j,2j,\ldots,100j\}$ has in total all digits in the set $\{1,2,\ldots,9\}$ for all $j \in \mathbb{Z} \cap [1,n]$ fixed. And this is true, let see why; if $j$ is a power of $10$ then our claim is trivial, since it is true for $j=1$ . Otherwise, define $\ell:=\{h \in \mathbb{N}:10^{h}<j<10^{h+1}\}$ . Since $100j>10^{\ell+2}$ and $j<10^{\ell+1}$ , then in every set $\mathbb{Z} \cap [k10^{\ell+1},(k+1)10^{\ell+1})$ there is at least one element of $S$ for all $k \in \mathbb{Z} \cap [1,9]$ fixed. But it means that the leftmost digit of such element of $S$ is exactly $k$ , for all $k \in \mathbb{Z} \cap [1,9]$ fixed. And it is enough to deduce that our claim is true. []

Problem 2- Extended sum of digits.

Let $(a,b,c,d,e) \in \mathbb{P}^4 \times \mathbb{N}$ such that $(a-2)(a-b)^2>0$ and define $s_b(\cdot)$ the sum of digit function in base $b \in \mathbb{N} \setminus\{0,1\}$ . Show that if $s_b(an+b)=s_b(cn+d)$ for all integer $n>e$ and $b \in \mathbb{Z} \cap (1,a)$ , then $a-c=b-d=0$ . (Gabriel Dospinescu)

Solution. For $t$ sufficiently large choose $n = \frac {i^{(k + 1)t} - 1}{i^t - 1} - 1$ , so $s_i(an + b) = ks_i(a)+s_i(b)=ks_i(c)+s_i(d)=s_i(cn + d)$ . But $k \mid s_i(b)-s_i(d)$ for all $k$ , so $s_i(b)=s_i(d)$ and $s_i(a)=s_i(c)$ for all $1<i<a$ . Choosing $i=a-1$ we obtain $2=s_{a - 1}(a)=s_{a - 1}(c)$ , so $c=(a - 1)^{\ell_1}+(a - 1)^{\ell_2}$ that is divisible by $a-1$ if $\ell_1\ell_2>0$ , otherwise divisible by $a$ (the case $\ell_1=\ell_2=0$ is trivial since $c = 2$ and $a$ would be a power of 2), that implies $a=c$ . Now if $b<a$ then $1=s_b(b)=s_b(d)$ so $b=d$ otherwise we can assume $d\ge b>a$ , so choosing enough large $i$ and enough large $j$ such that $2^i\mid aj + b$ we obtain $s_2(aj+b)=s_2(aj+d)=s_2(aj+b)+s_2(d-b)$ then $d=b$ .[]

Problem 3- Number of coprime subset of {1,2,..,n}

Show that $f(n):=|\{A \subset \{1,2\ldots,n\} \text{ s.t. } \text{gcd}(x \in A) = 1\}|$ is not a perfect square for all integer $n>1$ .

Solution. Define $g(n):=|\{A\subset \{1,2\ldots,n\}\text{ s.t. }n\in A\text{ and }\text{gcd}(x \in A)=1\}|$ for all $n \in \mathbb{N}_0$ ; here $*$ denotes the convolution product between two arithmetical function; define also $a(n):=2^{n-1}$ for all $n\in \mathbb{N}_0$ ; $b(n):=(-1)^n$ for all $n\in \mathbb{N}_0$ ; $u(n):=1$ for all $n\in \mathbb{N}_0$ , and $I(n):=\lfloor n^{-1}\rfloor$ for all $n\in \mathbb{N}_0$ . Clearly $\displaystyle f(n)=\sum_{i = 1}^n{g(i)}$ , and $g(1)=g(2)=1$ , and $a(n)=(g*u)(n)$ . By Moebius inversion and operating in $\mathbb{F}_3$ we have $g(n)=(a*\mu)(n)=-(b*\mu)(n)$ : if $n>2$ is odd then $g(n)=-(u*\mu)(n)=-I(n)=0$ ; if $n=2q$ for some odd $q>1$ then $g(n)=-(u*\mu)(q)-(u*\mu)(q)=- 2I(q)=0$ , otherwise $n=2^tq$ for some $t>1$ and $q>1$ odd, then $g(n)=-(u*\mu)(q)-\mu(2)(u*\mu)(q)=(u*\mu)(q)-(u*\mu)(q)=0$ . We have concluded that $f(n)=f(2)=2$ for all $n>1$ , but $\left(\frac {2}{3}\right)=-1$ , so $f(n)$ cannot be a perfect square.[]

Problem 4. A special case of Dirichlet theorem

Dirichlet theorem states that if $(a,b) \in \mathbb{N}^2$ is fixed such that $a>0$ and $b>1$ and defined $\mathbb{P}_{a,b}:=\{p \in \mathbb{P}:b \mid p-a\}$ , then $\displaystyle \sum_{p \in \mathbb{P}_{a,b}}{p^{-1}}$ diverges. The problem is: show the statement for $(a,b)=(1,4)$ .

Solution. Suppose that the statement is false, so we can define the number $\displaystyle x:=\min\{y \in \mathbb{N} \cap [100,+\infty): \sum_{p \in \mathbb{P}_{1,4}}{p^{-1}}<4^{-1}\text{ s.t. }y<p\}$ . Let $k \in \mathbb{N} \cap [x+1,+\infty)$ fixed and define also sets:

$A(k):=\{y \in \mathbb{N}:\exists z \in \mathbb{N} \cap [1,k]\text{ s.t. } y=4z^2+1\}$ ;

$B(k):=\{y \in \mathbb{N}:y \in A\text{ and }\text{gpf}(y)\ge x+1\}$ ;

$C(k):=A\setminus B=\{y \in \mathbb{N}:y \in A\text{ and }\text{gpf}(y) \le x\}$ ;

$D(k):=\{y \in \mathbb{N} \cap [1,k^4]:\upsilon_p(y)=0 \text{ for all } p \in \mathbb{P}_{3,4} \cup \{2\}\text{ and }\text{gpf}(y)\le x\}$ .

Obviusly $\upsilon_p(t)=0$ for all t in A(k) and $p \in \mathbb{P}_{3,4} \cup \{2\}$ and $C(k) \subseteq D(k)$ . Furthermore, if $t \in \mathbb{N}$ and $p \in \mathbb{P}_{1,4} \cap (x,k]$ are fixed, then in the set $\{t+1,t+2,\ldots,t+p\}$ there are at most $2$ solution of $p \mid 4x^2+1$ . And, again, we have that $|\{t+1,t+2,\ldots,t+12\} \cap \mathbb{P}_{1,4}\}| \le 2$ . It is enough to deduce that $\displaystyle |B(k)| \le \sum_{p \in \mathbb{P}_{1,4} \cap (x,k]}{\left(2\lceil kp^{-1} \rceil\right)} < 2k\left(\sum_{p \in \mathbb{P}_{1,4} \cap (x,k]}{p^{-1}}\right)+2\sum_{p \in \mathbb{P}_{1,4} \cap (x,k]}{1}<$ $\displaystyle 2k\left(\sum_{p \in \mathbb{P}_{1,4} \cap (x,+\infty)}{p^{-1}}\right)+2\sum_{p \in \mathbb{P}_{1,4} \cap [1,k]}{1} \le$ $\displaystyle 2k(4^{-1})+2(2k \cdot 12^{-1})=\frac{5k}{6}$ .

Now, we can show by PMI that if $k=2^{2^m}$ for some enough large $m \in \mathbb{N}$ then $|D(k)| \le 2^{x(m+2)}$ . If $m=0$ it is clear, then suppose that it is true for $m \in \mathbb{N}$ . For $k=2^{2^{m+1}}$ we’ll have that if $t \in D(2^{2^{m+1}})$ then $f(t)$ can be choosen in $2^r$ ways, where $r:=|\mathbb{P}_{1,4} \cap [1,x]|$ and $\displaystyle f(t):=\prod_{2\nmid \upsilon_p(t),p \in \mathbb{P}}{p}$ ; and $tf(t)^{-1}$ is clearly a square and $\displaystyle (tf(t)^{-1})^{\frac{1}{2}} \le 2^{2^m}$ can be choosen in $|D(2^{2^m})|\le 2^{x(m+2)}$ ways by assumption. It means that $|D(2^{2^{m+1}})| \le 2^r \cdot 2^{x(m+2)} \le 2^x \cdot 2^{x(m+2)}=2^{x(m+3)}$ , that is our aim.

It means that if $k=2^{2^{x-2}}$ then |D(k)| is not greater than the value $2^{x^2}$ $<\frac{k}{6}$ , but $\displaystyle k=|A(k)|=|B(k) \cup C(k)|=|B(k)|+|C(k)| \le |B(k)|+|D(k)| < \frac{5k}{6}+\frac{k}{6}=k$ , that is a contradiction. []

Problem 5- A inequality with Euler function and gcd(.)

Show that for all $(m,n) \in \mathbb{N}_0^2$ the inequality $\displaystyle \frac{\text{gcd}\left(\varphi(2^n+1),\varphi(2^m+1)\right)}{\varphi\left(\text{gcd}(2^n+1,2^m+1)\right)} \ge \frac{2\text{gcd}(m,n)}{2^{\text{gcd}(m,n)}}$ holds. (Nanang Susyanto)

Solution. Let $p \in \mathbb{P}\setminus \{2\}$ such that $p \mid \text{gcd}(2^n+1,2^m+1)$ . Define $(x,y) \in \mathbb{N}_0^2$ such that $x:=m\text{gcd}(m,n)^{-1}$ and $y:=n\text{gcd}(m,n)^{-1}$ .So there exist $(c,d) \in \mathbb{N}^2$ such that $\displaystyle x=\left(\frac{\text{ord}_p(2^{\text{gcd}(m,n)})}{2}\right)(2c+1)$ and $\displaystyle y=\left(\frac{\text{ord}_p(2^{\text{gcd}(m,n)})}{2}\right)(2d+1)$ . So we must have $2 \mid \text{ord}_p(2^{\text{gcd}(m,n)})$ and since by construction $\text{gcd}(x,y)=1$ then $\text{ord}_p(2^{\text{gcd}(m,n)})=2$ , and it is equivalent to say that $p \mid 2^{2\text{gcd}(m,n)}+1$ , and $p \nmid 2^{\text{gcd}(m,n)}-1$ , that is $p \mid 2^{\text{gcd}(m,n)}+1$ . Let $\displaystyle 2^{\text{gcd}(m,n)}+1=\prod_{1\le i\le k}{q_i^{a_i}}$ be its canonical factorization, then by Lifting lemma we know that $\upsilon_{q_i}\left(2^m+1\right)=a_i+\upsilon_{q_i}(x)$ and $\upsilon_{q_i}\left(2^n+1\right)=a_i+\upsilon_{q_i}(y)$ for all $i \in \mathbb{Z} \cap [1,k]$ . But by construction $\min\{\upsilon_{q_i}(x),\upsilon_{q_i}(y)\}=0$ , so $\upsilon_{q_i}\left(\text{gcd}(2^m+1,2^n+1)\right)=a_i$ . It is sufficient to deduce that $\varphi\left(\text{gcd}(2^n+1,2^m+1)\right) \le \text{gcd}(2^n+1,2^m+1)-1 \le 2^{\text{gcd}(m,n)}$ . So, it is enough to show that $\displaystyle \text{gcd}\left(\varphi(2^n+1),\varphi(2^m+1)\right) \ge 2\text{gcd}(m,n)$ to conclude the problem.

We claim that $2\text{gcd}(m,n) \mid \text{gcd}\left(\varphi(2^n+1),\varphi(2^m+1)\right)$ , and it is enough to show that for all $(a,b,c) \in \mathbb{N}_0^3$ s.t. $b>c$ the relation $2a \mid \varphi(b^a+c^a)$ holds. In fact if $\alpha \mid \beta$ for some $(\alpha.\beta) \in \mathbb{N}_0^2$ then $\varphi(\alpha) \mid \varphi(\beta)$ so we can assume wlog $\text{gcd}(b,c)=1$ . Define $d:=b^a+c^a$ and $e:=bc^{-1}$ in $\mathbb{Z}/d\mathbb{Z}$ , so $\text{gcd}(b,d)=\text{gcd}(c,d)=\text{gcd}(e,d)=1$ . We have by construction that $d \mid e^a+1$ , so the smallest $k \in \mathbb{N}$ such that $d \mid x^k+1$ is $a$ . Now we have $b^a+c^a=d \mid e^{\text{ord}_d(e)}-1=b^{\text{ord}_d(e)}-c^{\text{ord}_d(e)} < b^{\text{ord}_d(e)}+c^{\text{ord}_d(e)}$ , so ${\text{ord}_d(e)}>a$ . If $a<\text{ord}_d(e)<2a$ then in $\mathbb{Z}/d\mathbb{Z}$ we have $1=e^a \cdot e^{\text{ord}_d(e)-a}$ so $-1=e^{\text{ord}_d(e)-a}<e^a$ , that is impossible. So we have $\text{ord}_d(e) \ge 2a$ . Obviusly $a \neq \text{ord}_d(e) \mid 2a$ , so $\text{ord}_d(e)=2a$ . And because $e^{\varphi(d)} \equiv 1 \pmod d$ we conclude that $2a \mid \varphi(d)=\varphi(b^a+c^a)$ , that is our aim. []

Problem 6- A functonal with cubes

Find all function $f(\cdot) \mathbb{Z} \to \mathbb{Z}$ such that $f(x^3+y^3+z^3)=f(x)^3+f(y)^3+f(z)^3$ for all $(x,y,z) \in \mathbb{Z}^3$ .

Solution. Define $g(\cdot):\mathbb{Z}^3 \to \mathbb{Z}:(x,y,z) \to f(x^3+y^3+z^3)-f(x)^3+f(y)^3+f(z)^3$ then $g(\cdot)$ is identically null. Now $g(0,0,0)=0$ implies that $f(0)=0$ and $0=g(0,0,z)=g(x,-x,z)$ for all $(x,z) \in \mathbb{Z}^2$ implies that $f(\cdot)$ is a odd function. Define $k:=f(1)$ , then $g(1,0,0)=0$ implies that $k \in \{-1,0,1\}$ . Now $g(1,1,0)=0$ and $g(1,1,1)=0$ respectively imply that $f(2)=2k$ and $f(3)=3k$ . We claim now that all and only functions $f(\cdot)$ that we are searching are $f(x)=kx$ for all $x \in \mathbb{Z}$ for some $k \in \{-1,0,1\}$ fixed. Since $f(\cdot)$ is odd, it is enough to check that $f(x)=kx$ for all $x \in \mathbb{N}$ . We have that $g(4,-3,-3)=g(2,1,1)=0$ so $f(4)=4k$ , $g(5,-4,-4)=g(1,1,1)=0$ so $f(5)=5k$ , $g(6,-5,-4)=g(3,0,0)=0$ so $f(6)=6k$ and $g(7,-6,-5)=g(1,1,0)=0$ so also $f(7)=7k$ . Suppose now the we have proved the statement for all $y \in \mathbb{Z} \cap [-2t+1,2t-1]$ for some t in $\mathbb{Z} \cap [4,+\infty)$ .Let’s prove the statement for $t+1$ by PMI: in fact since $\exists (z_1,z_2,z_3,z_4,z_5) \in \mathbb{Z}^5$ such that $\max\{|z_1|,|z_2|,|z_3|,|z_4|,|z_5|\}<t$ and $z_1^3+z_2^3+z_3^3+z_4^3+z_5^3=t$ , so $g(2t,-2z_1,-2z_2)=g(2z_3,2z_4,2z_5)=0$ that means $f(2t)=2tk$ and finally $g(2t+1,1-2t,-4-t)=g(4-t,-1,-5)=0$ so also $f(2t+1)=k(2t+1)$ , and the induction is complete. []

Problem 7- A strange divisibility

Let $p\in \mathbb{P}$ fixed such that $12\mid p-5$ ; show that $\displaystyle p\mid \left(\prod_{i \in \mathbb{Z} \cap [1,\frac{p-3}{2}]}{(i^2+i+1)}\right)+2$ .

Solution. Working in $\mathbb{Z}/p\mathbb{Z}$ we have that $\displaystyle \prod_{i \in \mathbb{Z} \cap [1,\frac{p-3}{2}]}{(i^2+i+1)}=2^{p-1}\prod_{i \in \mathbb{Z} \cap [1,\frac{p-3}{2}]}{(i^2+i+1)}$ $\displaystyle =(1^2+3)\prod_{i \in \mathbb{Z} \cap [1,\frac{p-3}{2}]}{(4i^2+4i+4)}$ $\displaystyle =\prod_{i \in \mathbb{Z} \cap [1,\frac{p-1}{2}]}{\left((2i-1)^2+3\right)}$ $\displaystyle =\prod_{i \in \mathbb{Z} \cap [1,\frac{p-1}{2}]}{(i^2+3)}:=S$ and by Euler criterion we have that the constant term of the polynomial $\displaystyle p(x):=(x-3)^{\frac{p-1}{2}}-1$ is $S$ , so we can conclude $\displaystyle S=p(0)=\left(\frac{3}{p}\right)-1=-2$ . []

Problem 8- Minimal sum and difference with primes

Let $p_i$ the $i$ -th prime of $\mathbb{P}$ and $n\in \mathbb{N} \setminus\{0,1\}$ a fixed integer. Find, if it exists, the smallest absolute constant $K$ such that $\displaystyle \left|\sum_{i \in \mathbb{N} \cap [1,n]}{e_ip_i}\right| \le K$ for at least one choose of $e_1,e_2,\ldots,e_n \in \{-1,1\}$ .

Solution. We claim that $K$ exists and it is $1$ . Define $\displaystyle K_n:=\min\{x \in \mathbb{N}:\exists e_1,e_2,\ldots,e_n \in \{-1,1\}\text{ s.t. }\left|\sum_{i \in \mathbb{N} \cap [1,n]}{e_ip_i}\right|=x\}$ , and obviusly $K$ will be $\max\{K_1,K_2,\ldots\}$ for all $n\in \mathbb{N}\setminus\{0,1\}$ . It is enough to prove that $K_n$ is $1$ if $n$ is even, otherwise is $0$ (note that if $2 \mid n$ then $K_n \ge 1$ since the required sum is invariant modulo $2$ ). Let’s begin with some cases and complete the proof by PMI showing that if $n$ is fixed, then we can obtain (by a suitable choice of $e_1,e_2,\ldots,e_n \in \{-1,1\}^n$ ) all integer $y \in \mathbb{Z} \cap [0,2p_n]$ such that $2 \mid n+1-y$ . If $n=2$ then trivially $k_2=1$ since we can choose $(e_1,e_2)=(-1,+1)$ . If $n=3$ then $k_3=0$ since we can choose $(e_1,e_2,e_3)=(-1,-1,+1)$ . If $n=4$ then $k_4=1$ since we can choose $(e_1,e_2,e_3,e_4)=(+1,-1,-1,+1)$ . If $n=2$ then $k_5=0$ since we can choose $(e_1,e_2,e_3,e_4,e_5)=(+1,-1,+1,+1,-1)$ . With $n=6$ we can obtain all odd integers in the interval $[0,+2 \cdot 13]$ (in truth, if $n<6$ we can find always counterxamples), in fact it is enough to see that: $k_6=1=-2+3+5-7-11+13$ , $3=+2-3-5+7-11+13$ , $5=+2+3+5-7-11+13$ , $7=-2-3-5-7+11+13$ , $9=-2-3+5+7-11+13$ , $11=-2-3+5+7-11+13$ , $13=+2-3+5+7-11+13$ , $15=-2+3+5+7-11+13$ , $17=+2+3-5-7+11+13$ , $19=+2+3+5+7-11+13$ , $21=-2-3-5+7+11+13$ , $23=-2+3+5-7+11+13$ , $25=+2-3-5+7+11+13$ . Now, remembering that $p_{n+1}<2p_n$ (Bertand postulate), we can obtain all integers with the parity of $n$ of the intervals $[-2p_n+p_{n+1},2p_n+p_{n+1}]$ (choosing $e_{n+1}=+1$ ) and of $[-2p_n-p_{n-1},2p_n+p_{n+1}]$ (choosing $e_{n+1}=-1$ ). But the interval $[-2p_{n+1},2p_{n+1}]$ is a subset of their union, so the induction is complete. []

Problem 9- When n^2 +1 divides n!

Show that $\displaystyle \frac{n!}{n^2+1} \in \mathbb{Z}$ for some $n \in \mathbb{N}_0$ if and only if the proposition i) and ii) are both false:

i) $\text{gpf}(n^2+1)>n$ ;

ii) $\displaystyle \left(\frac{n^2+1}{2}\right)^{\frac{1}{2}}:=p \in \mathbb{P}$ .

Solution. Part 1: “only if”. If $\displaystyle \frac{n!}{n^2+1} \in \mathbb{Z}$ for some $n \in \mathbb{N}_0$ then clearly $\text{rad}(n^2+1) \mid \text{rad}(n!)$ and in particular $\text{gpf}(n^2+1)\le\text{gpf}(n)\le n$ , that contradicts the proposition i). On the other hand, if $\displaystyle \left(\frac{n^2+1}{2}\right)^{\frac{1}{2}}:=p \in \mathbb{P}$ then it should be $p^2 \mid 2p^2=n^2+1\mid n!=\left(\sqrt{2p^2-1}\right)!$ and in particular $\left(\sqrt{2p^2-1}\right)\ge 2p$ , that is false for all $p \in \mathbb{P}$ . Part 2: “if”. If $\text{gpf}(n^2+1)\le n$ and $\displaystyle \left(\frac{n^2+1}{2}\right)^{\frac{1}{2}}\not\in \mathbb{P}$ then we want to show that $n!\vdots n^2+1$ . Remember that $x^2+1$ is never a non-trivial power of some positive integers. In fact, if $x^2+1=y^n$ for some positive integer $x,y,n$ , then $x$ is even (otherwise modulo $4$ we should have $n\mid 1=\upsilon_2(x^2+1)$ ). But working in the extension $\mathbb{Z}[i]$ we have $\text{gcd}(x+i,x-i)=1$ , so they are both $n$ -power. So it must exist $(a,b) \in \mathbb{Z}^2$ such that $(a+bi)^n=x+i$ , but seeing the $i$ -coefficient we must have $(a,b)=(0,-1)$ , from which the unique trivial solution $(x,y)=(0,1)$ follows. In particular since $n^2+1 \not\in \mathbb{P}$ then $\omega(n^2+1) \ge 2$ . Part2/case1: $2 \nmid n$ . We have $\upsilon_2(n^2+1)=1 \le \upsilon_2(n!)$ . Let $p \in \mathbb{P} \cap [3,n]$ fixed: if $\upsilon_p(n^2+1)=1$ then $\upsilon_p(n^2+1) \le \upsilon_p(n!)$ ; if $\upsilon_p(n^2+1)=2$ then there exist $q \in \mathbb{P} \cap [3,n]$ such that $(p-q)^2>0$ and $2p^2q \mid n^2+1$ : in particular we have $n \ge \sqrt{2p^2q-1} \ge 2p$ since $2p^2q-1 \ge 4p^2$ iff $2p^2(q-2) \ge 1$ , and it shows that $\upsilon_p(n^2+1)=2 \le \upsilon_p(n!)$ ; otherwise $\upsilon_p(n^2+1):=z\ge 3$ then we have $2p^z \mid n^2+1$ and so $n \ge \sqrt{2p^z-1}$ . It is enough to show that $\displaystyle \sqrt{2p^z-1} \ge pz$ . But if a prime $r$ divides $n^2+1$ then $4 \mid r-1$ and then $r \ge 5$ . And so the inequality $2p^{z-2}\ge 2\cdot 5^{z-2}>z^2$ holds for all integer $z \ge 3$ since $2\cdot 5>3^2$ and if it is true for $z\in \mathbb{N}\cap [3,+\infty)$ then $2\cdot 5^{z-1}>5z^2>(z+1)^2$ , that is true. Part2/case2: $2 \mid n$ . We have now $\upsilon_2(n^2+1)=0$ , so the condition on proposition ii) is never satisfied. Let $p \in \mathbb{P} \cap [3,n]$ fixed: if $\upsilon_p(n^2+1)=1$ then $\upsilon_p(n^2+1) \le \upsilon_p(n!)$ ; if $\upsilon_p(n^2+1)=2$ then there exist $q \in \mathbb{P} \cap [3,n]$ such that $(p-q)^2>0$ and $p^2q \mid n^2+1$ : in particular we have $n^2+1\ge 5p^2$ and the conclusion is the same as in part2/case1; otherwise $\upsilon_p(n^2+1):=z\ge 3$ then we have $n^2+1 \ge 5p^z > 2p^z$ and the conclusion is the same as in part2/case1 again. []

Problem 10- A condition for being a covering system

If $1<k_1<k_2<\ldots<k_n$ and $a_1,a_2,\ldots,a_n$ are fixed integers such that for all $x \in \mathbb{Z}$ there exist $i \in \mathbb{N} \cap [1,n]$ that satisfy $k_i \mid x+a_i$ , then find the smallest possible value of the positive integer $n$ . (Turkey National Math Olympiad 2009)

Solution. We claim that the required number is $n=5$ .
Assume by contradiction that for $n=4$ we can find integers $1<k_1<k_2<k_3<k_4$ and $(a_1,a_2,a_3,a_4) \in \mathbb{Z}^4$ s.t. $\{x \equiv a_i \pmod{k_i}\}_{1 \le i \le 4}$ is a covering system. Obviusly we must have that the system $\{x \equiv a_i \pmod{k_i}\}_{1 \le i \le 4}$ covers all residue classes in $\mathbb{Z}/\text{lcm}(k_1,k_2,k_3,k_4)\mathbb{Z}$ , and if $\text{gpf}\left(\text{lcm}(k_1,k_2,k_3,k_4)\right):=p \in \mathbb{P}\setminus \{2,3\}$ then we cannot have a covering system since each congruence can cover at most one of the $p$ class residues. At the same way if $\text{gpf}(k_1k_2k_3k_4)=2$ then there exists a residue class $x$ in $\mathbb{Z}/k_4\mathbb{Z}$ that is not covered. Now $\text{lpf}\left(\text{lcm}(k_1,k_2,k_3,k_4)\right)=2$ since if $k_1>2$ then $\displaystyle \sum_{i \in \mathbb{N} \cap [1,4]}{k_i^{-1}} \le$ $\displaystyle \sum_{i \in \mathbb{N} \cap [3,6]}{i^{-1}}<1$ , that is absurd. It means that $\text{rad}(k_1k_2k_3k_4)$ is exactly $6$ . Now we must have that the system $\{x \equiv a_i \pmod{k_i}\}_{2 \le i \le 4}$ convers all $\mathbb{Z}/3\mathbb{Z}$ and clearly we need have $9 \nmid \text{lcm}(k_2,k_3,k_4)$ and $3 \mid \text{gcd}(k_2,k_3,k_4)$ . Now we must have $k_2=3$ and $k_3=6$ since otherwise $\displaystyle \sum_{i \in \mathbb{N} \cap [1,4]}{k_i^{-1}} \le$ $\displaystyle 2^{-1}+3^{-1}+12^{-1}+24^{-1}<1$ , that is absurd. So there exist $\alpha \in \mathbb{N} \setminus \{0,1\}$ such that $(k_1,k_2,k_3,k_4)=(2,3,6,3\cdot 2^{\alpha})$ , but we have always $12 \mid k_4$ , so if $(k_1,k_2,k_3,k_4)$ exists then it is $(2,3,6,12)$ : but in $\mathbb{Z}/12\mathbb{Z}$ we have that the system $\{x \equiv a_i \pmod{k_i}\}_{1 \le i \le 3}$ covers at most $\left(\frac{12}{2}+\frac{12}{3}-\frac{12}{6}\right)+\frac{12}{6}-1=9$ residue class, and the last one $x \equiv a_4 \pmod{12}$ is not enough to close such bug. On the other hand $(k_1k_2,k_3,k_4,k_5)=(2,3,4,6,12)$ and $(a_1,a_2,a_3,a_4,a_5)=(0,2,1,1,3)$ is a covering system. []

Problem 11- Only a few element in harmonic sum determine its divergence

Let $k\in \mathbb N_0$ fixed and $N$ be the set of numbers such that $k$ doesn’t occur in their decimal representation, then $\displaystyle S:=\sum_{n\in N}n^{-1}<+\infty$ .

Solution. Define $y:=\frac{1}{\lfloor Log_{10}(k) \rfloor +1}$ the reciprocal of number of digits of $k$ and $N(h):=N\cap [10^h,10^{h+1})$ for all $h\in \mathbb{N}$ then $\displaystyle S=\sum_{h \in \mathbb{N}}{\left(\sum_{n\in N(h)}{n^{-1}}\right)}\le$ $\displaystyle \sum_{h \in \mathbb{N}}{\left(\frac{|N(h)|}{10^h}\right)}$ $\displaystyle \le \sum_{h \in \mathbb{N}}{\left(\frac{10^{h-\lfloor hy \rfloor}9^{\lfloor hy \rfloor}}{10^h}\right)}$ $\displaystyle \le \sum_{h \in \mathbb{N}}{\left(\frac{10^{h- hy +1}9^{hy-1}}{10^h}\right)}$ $=\displaystyle \sum_{h \in \mathbb{N}}{\left(\frac{9}{10}\right)^{hy-1}}<+\infty$ . Corollary: since $\sum_{p \in \mathbb{P}}{p^{-1}}$ is not convergent,then there exist infinitely many primes that contains $k$ in its decimal representation. []

Problem 12- A equation involving Euler Phi-part 1

Find all $n \in \mathbb{N}_0$ such that $n-\varphi(n)=402$ .

Solution. Since $2 \mid \varphi(n)$ for all $n \in \mathbb{N}\setminus\{0,1,2\}$ we have that $2\mid n$ , so the chain of inequalities $\frac{n}{2} \le n-\varphi(n)=402 \le n$ holds, so if $m:=\frac{n}{2} \in \mathbb{N}$ then $m \in \mathbb{Z}\cap [201,402]$ . Since $402$ is not a power of $2$ then $n$ cannot be a power of $2$ , so $\omega(n) \ge 2$ . Now if $2 \mid m$ then $4 \mid \text{gcd}(n,\varphi(n)) \mid 402$ that is a contradiction, so $\upsilon_2(n)=1$ , i.e. $m$ is odd. Suppose that $\upsilon_p(n) \ge 2$ for some $p \in \mathbb{P}$ then $p \mid \text{gcd}(n,\varphi(n))\mid 402$ that is $p \in \{3,67\}$ ; and it is easy to see that $\upsilon_{67}(n) \le 1$ since otherwise $67^2 \le m \le 402$ that is false. If $m \in \mathbb{P}$ then $2m-(m-1)=402$ i.e. $m=401 \in \mathbb{P}$ , so $n=802$ is a solution. From now suppose that $m$ is not prime. If $\upsilon_3(n)=0$ then $\omega(m) \le 2$ since otherwise also $\upsilon_3(\varphi(m))=0$ i.e. if $p \in \mathbb{P}$ divides $m$ then $3 \mid p+1$ and so $5 \cdot 11 \cdot 17 \le m \le 402$ that is again a contradiction. So $2m-\varphi(m)=402$ and $|\mu(m)|=1\text{ and }\upsilon_2(m)=\upsilon_3(m)=0$ . So there exist primes $p>q>3$ such that $m=pq$ and $2m-\varphi(m)=402$ , i.e. $(p+1)(q+1)=4 \cdot 101$ that is absurd. It proves if $n$ is a solution then $3 \mid n$ . Define $\displaystyle t:=\frac{n}{6}=\frac{m}{3}$ : if it prime then $6t-2\varphi(t)=402$ , i.e. $t=100$ , contradiction. If $\upsilon_3(n) \ge 3$ then $3^2 \mid \text{gcd}(n,\varphi(n)) \mid 402$ , contradiction; case 1: if $3 \mid t$ and $r:=\frac{t}{3}$ then $\upsilon_3(r)=0$ and $r \not \in \mathbb{P}$ (as above), so we are lead to $3r-\varphi(r)=67$ with $r \in \{25,35\}$ , and they are not solution. Case 2: $3t-\varphi(t)=201$ with $\upsilon_2(t)=\upsilon_3(t)=0$ , $|\mu(t)|=1$ and $t \in \left(\mathbb{Z} \cap [67,134]\right) \setminus \mathbb{P}$ . If $\omega(t) \ge 3$ then $5 \cdot 7 \cdot 11 \le t \le 134$ that is false, so there exist primes $p>q>3$ such that $t=pq$ . It leads to $(2p+1)(2q+1)=405$ and the unique solution is clearly $(p,q)=(13,7)$ . We have shown that $n-\varphi(n)=402$ for some positive integer $n$ if and only if $n \in \{546,802\}$ . []

Problem 13- A equation involving Euler Phi-part 2

Find all $n \in \mathbb{N}_0$ such that $n-\varphi(n)=420$ .

Solution. Since $2 \mid \varphi(n)$ for all $n \in \mathbb{N}\setminus\{0,1,2\}$ we have that $2\mid n$ , so the chain of inequalities $\frac{n}{2} \le n-\varphi(n)=420<n$ holds, so if $m:=\frac{n}{2} \in \mathbb{N}$ then $m \in \mathbb{Z}\cap [211,420]$ . Since $420$ is not a power of $2$ then $n$ cannot be a power of $2$ , so $\omega(n) \ge 2$ . Note also that $\upsilon_p(420)=\upsilon_p(n-\varphi(n)) \ge \upsilon_p(n)-1$ that is $\max\{\upsilon_3(n),\upsilon_5(n),\upsilon_7(n)\}\le 2$ and $\upsilon_p(n)\le 1$ for all $p\in \mathbb{P}\setminus\{2,3,5,7\}$ . If $2^4 \mid n$ then $2^3 \mid \text{gcd}(n,\varphi(n))\mid 420$ ,contradiction and if $\upsilon_2(n)=3$ then $2^3 \mid \text{gcd}(n,\varphi(n))\mid 420$ again, since $n>8$ implies $\displaystyle \sum_{p\in \mathbb{P}\setminus\{2\}}{\upsilon_p(n)}>0$ ,contradiction. Case 1. If $\upsilon_2(n)=1$ then $2m-\varphi(m)=420$ and $m \in 2\mathbb{Z}+1 \cap [211,419]$ . Now $1=\upsilon_2(2m-420)=\upsilon_2(\varphi(m))$ implies that $\omega(m)=1$ : if $m \in \mathbb{P}$ then $2m-(m-1)=420$ , i.e. $m=419 \in \mathbb{P}$ , that is a solution, otherwise it can only be a square of a prime and $211\le m\le 7^2$ , contradiction. Case 2. If $\upsilon_2(n)=2$ and $h:=\frac{n}{4} \in 2\mathbb{Z}+1\cap[107,209]$ then $2h-\varphi(h)=210$ . Now $\displaystyle \sum_{p\in \mathbb{P}\setminus\{2\}}{\upsilon_p(h)}\le 3$ since otherwise $209 \ge h \ge 3^2\cdot 5^2$ , that is false. In particular it implies that $\omega(h) \le 3$ . If $\omega(h)=1$ and $h\in \mathbb{P}$ then $2h-(h-1)=210$ , i.e. $h=209\not\in \mathbb{P}$ , otherwise, as before, it can only be a square of a prime and $107 \le h \le 7^2$ , contradiction. If $\omega(h)=2$ and $h=pq$ for some primes $p>q>2$ then $2pq-(p-1)(q-1)=210$ , i.e. $(p+1)(q+1)=2^2 \cdot 53$ and it has no solution; otherwise $h=pq^2$ for some distinct odd primes $p,q$ such that $q \in \mathbb{P}\cap[3,7]$ , so we have $2pq^2-pq(q-1)=210$ , i.e. $\displaystyle p=\frac{210-q(q-1)}{q(q+1)}$ . Now in $\mathbb{Z}/(q+1)\mathbb{Z}$ we have $0=210-q(q-1)=208$ , so $q=5$ cannot lead to some solution. We can also easily see that $q \in \{3,7\}$ lead both to solutions $n\in\{2^2\cdot 3\cdot 7^2,2^2\cdot 3^2 \cdot 17\}$ . It remains only the last case $\omega(h)=3$ , so $h=pqr$ for some primes $p>q>r>2$ . So the equation becomes $2pqr-(p-1)(q-1)(r-1)=210$ , but $210=(p+1)(q+1)(r+1)-2(p+q+r)$ $\ge (p+1)(5+1)(6+1)-2(3p-6)=18p+36$ , that is false for all $p\in \mathbb{P}\setminus\{2,3,5,7\}$ ; otherwise we must have $(p,q,r)=(7,5,3)$ and so $p_4\#-2\cdot 4\cdot 6=210$ , but $0=\upsilon_5(p_4\#-2\cdot 4\cdot 6)<\upsilon_5(210)=1$ , contradiction. We have shown that $n-\varphi(n)=402$ for some positive integer $n$ if and only if $n \in \{588,612,838\}$ . []

Problem 14- A strictly increasing sequence

Let $\{a_i\}_{i\in \mathbb{N}_0}$ a strictlyincreasing sequence of positive integers such that $a_k\neq a_i+a_j$ for all $1\le i\le j\le k-1$ . Then $\sum_{1\le i\le n}{a_i}\le a_n^2-n^2+n$ . (Carlo Sanna)

Solution. We assume to demonstrate it for all $n\ge 3$ . Let $\{a_k\}_{k \in \mathbb{N}_0}$ a strictly increasing sequence of positive integers such that $\displaystyle \prod_{1\le i\le j\le k}{(a_k-a_i-a_j)^2}>0$ and define $A_n:=\mathbb{Z}\cap [(2n-1)a_1,(2n+1)a_1)$ for all $n\in \mathbb{N}_0$ . Let $B$ the (numerable) set $\{n\in \mathbb{Z}:\exists i\in \mathbb{N}_0\text{ such that }a_i=n\}$ , then by assumption $|A_n \cap B|\le a_1$ . It means that in worst case we would have $\displaystyle a_n \ge \left(2\left\lfloor\frac{n}{a_1}\right\rfloor+1\right)a_1+\left(n-a_1\left\lfloor\frac{n}{a_1}\right\rfloor \right)$ $\displaystyle =\left(\left\lfloor\frac{n}{a_1}\right\rfloor+1\right)a_1+(n-1)$ . It means that $\displaystyle a_n^2-\sum_{i \in \mathbb{Z}\cap [1,n]}{a_i}\ge$ $\displaystyle \sum_{i \in \mathbb{Z}\cap [1,n]}{(a_n-a_i)}+\left(\left\lfloor\frac{n}{a_1}\right\rfloor a_1+a_1-1\right)a_n$ $\displaystyle \ge \sum_{i \in \mathbb{Z}\cap [1,n]}{(n-i)}+\left(\left(\frac{n}{a_1}-1\right)a_1+a_1-1\right)a_n$ $\displaystyle =\binom{n}{2}+(n-1)a_n$ . So it is enough to show that $\binom{n}{2}+(n-1)a_n \ge \binom{n}{2}$ , that is $a_n \ge \frac{n}{2}$ , but it is trivial since $\{a_i\}_{i \in\mathbb{N}_0}$ is a strictly increasing sequence.

Remark: The inequality $\displaystyle \sum_{i\in \mathbb{N}\cap [1,n]}{a_i}\le a_n^2-K(n^2-n)$ is true for $K\in \mathbb{R}\cap (-\infty,\frac{13}{6}]$ . In fact, as before, $\displaystyle a_n \ge \left(\left\lfloor \frac{n}{a_1}\right\rfloor+1\right)a_1+(n-1)$ $\ge \displaystyle \left(\frac{n}{a_1}\right)a_1+(n-1)=2n-1$ , so the last inequality $a_n\ge \frac{n}{2}$ can be replaced by $a_n \ge 2n-1$ . It means that $\displaystyle a_n^2-\sum_{i\in \mathbb{N}\cap [1,n]}{a_i}\ge \binom{n}{2}+(n-1)(2n-1)=(n-1)\left(\frac{5}{2}n-1\right)\ge \frac{13}{6}(n^2-n)$ for all $n\ge 3$ .

Corollary:Define the sequence $b_1:=a_1$ and $b_{n+1}^2:=b_n^2+b_n+2n$ for all $n \in \mathbb{N}\setminus\{0,1\}$ . Then $a_n\ge b_n$ for all positive integers $n$ . For $n=1$ it is trivially true. Suppose it is true for all $n \in \mathbb{Z}\cap [1,m-1]$ . Then, by PMI, we want to show that $a_m\ge b_m$ . Summing all identities we have that $\displaystyle b_m^2=a_1^2+\sum_{i \in \mathbb{N}\cap[1,m-1]}{b_i}+(n^2-n)\le a_1^2+\sum_{i \in \mathbb{N}\cap[1,m-1]}{a_i}+(n^2-n)$ . So it is enough to show that $\displaystyle a_n^2-a_1^2\ge \sum_{i \in \mathbb{N}\cap[1,m-1]}{a_i}+(n^2-n)$ . Since $\displaystyle a_n \ge \left(\left\lfloor\frac{n}{a_1}\right\rfloor+1\right)a_1+(n-1)$ , we have that it is enough that $\displaystyle a_1\left(\left\lfloor\frac{n}{a_1}\right\rfloor a_1+n-1\right)+a_1a_n\left\lfloor\frac{n}{a_1}\right\rfloor \ge \binom{n}{2}$ . If $a_1\ge n$ then rhs is at least $a_1(n-1)\ge n(n-1)\ge \binom{n}{2}$ . On the other hand, if $1\le a_1\le n-1$ then we have prove that $a_n(n-a_1)+a_1(n-a_1+n-1)\ge\binom{n}{2})$ ; the right hand side is a quadratic function in $a_1$ and with negative coefficients of degree 1 and 2 (taking in mind that $a_n\ge 2n-1$ ): it means that it is a decresing function in $a_1$ , so it is enough to prove the inequality for the worst case, $a_1=n-1$ . So we are lead to prove that $a_n+n(n-1)\ge \binom{n}{2}$ , that is obvious. []

Problem 15- A generalization from IMO99

Find all $(n,p)\in\mathbb{N}_0\times \mathbb{P}$ such that $n^{p-1}\mid (p-1)^n+1$ .

Solution. Trivially $(1,p)\in S:=\{(n,p)\in\mathbb{N}_0\times \mathbb{P}:n^{p-1}\mid (p-1)^n+1\}$ . If $p=2$ then $n \mid 1^n+1$ implies that also $(2,2)\in S$ . If $p=3$ then we should have that $n^2\mid 2^n+1$ . Obviusly $n\in \mathbb{N}\setminus 2\mathbb{N}$ so that $q:=\text{lpf}(n)\in \mathbb{P}\setminus\{2\}$ ; and since $\text{gcd}(q,2)=1$ we have that $q\mid \text{gcd}(2^{2n}-1,2^{q-1}-1)=2^{\text{gcd}(2n,q-1)}-1=2^2-1$ we have that $q=3$ . Now since $n^2\mid 2^n+1\mid 4^n-1$ we have that $2\upsilon_3(n)\le \upsilon_3(4^n-1^n)=\upsilon_3(n)+1$ so we have $\upsilon_3(n)=1$ . Define $r:=\text{lpf}(n3^{-1}) \in \mathbb{P}\setminus \{2,3\}$ , and if it is not defined then $(3,3)\in S$ . As before $r\mid \text{gcd}(2^{2\cdot (3r \cdot \frac{n}{3r})}-1,2^{r-1}-1)=2^{\text{gcd}(6,r-1)}-1$ . In particular $r\mid 2^{\text{gcd}(6,r-1)}-1\mid 2^6-1=3^2\cdot 7$ implies that $r=7$ . So if another solution with $p=3$ exists then $7\mid n^2\mid 2^n+1$ for some $n\in \mathbb{N}_0$ but $\text{ord}_7(2)=3 \in \mathbb{N}\setminus 2\mathbb{N}$ , that is a contradiction. Now we can suppose that $p\in \mathbb{P}\setminus\{2,3\}$ . As before, define $q:=\text{lpf}(n) \in \mathbb{P}\setminus\{2\}$ , then $q\mid q^{p-1}\mid n^{p-1}\mid (p-1)^n+1\mid (p-1)^{2n}-1$ , and on the other side, since obviusly $\text{gcd}(q,p-1)=1$ ,then $q\mid (p-1)^{q-1}-1$ . It means that $q\mid (p-1)^{\text{gcd}(q-1,2n)}-1=p(p-2)$ . If $q=p$ then $(p-1)\upsilon_p(n)=\upsilon_p(n^{p-1})\le \upsilon_p((p-1)^n-(-1)^n)=\upsilon_p(n)+1$ that is absurd since $p\ge 5$ . Otherwisev $q\mid p-2$ and we have at the same time $(p-1)\upsilon_q(n)\le \upsilon_q((p-1)^{2n}-1^{2n})=\upsilon_q(p-2)+\upsilon_q(2n)=\upsilon_q(p-2)+\upsilon_q(n)$ , that is $p-2\le (p-2)\upsilon_q(n) \le \upsilon_q(p-2)$ that is clearly absurd. []

Comments (2)

30/10/2009

Arbitrary large gap in the image of Euler function

Filed under: Mathematical matters — bboyjordan @ 3:38 AM

For all $k \in \mathbb{N}$ there exist $n \in \mathbb{N}_0$ such that $\varphi(\mathbb{N}_0) \cap [n,n+k]=\emptyset$ . (Salvatore Tringali)

Solution. Define the aritmetical function $f(\cdot):\mathbb{N}_0 \to \mathbb{N}:x \to |\varphi(\mathbb{N}_0) \cap [1,x]|$ . Note that the statement is equivalent to $f(x)=o(x)$ . Let’s begin with some estimates about $f(\cdot)$ .

We have that $2^{\omega(n)-1} \mid \varphi(n)$ for all $n \in \mathbb{N} \setminus \{0,1\}$ since $\varphi(\cdot)$ is a multiplicative aritmetical function and $\omega(n)-1$ is a lower bound for the number of distinct odd prime factor of $n$ . And define the set of functions $g_i(\cdot):\mathbb{N}_0 \to \mathbb{N}:x \to |\{y \in \mathbb{N}\cap [1,x]: \omega(y)=i\text{ and } |\mu(y)|=1\}|$ where $i \in \mathbb{N}_0$ . Let $(m,n) \in \mathbb{N}\times \mathbb{N}_0$ fixed and define also the set $S_{m,n}:=\{ j2^i : (i,j) \in \mathbb{N}^2 \text{ and } i \le m, 2\nmid j \le n2^{-i}\}$ .

Clearly $\displaystyle |S_{m,n}|=\sum_{0 \le i \le m}{\lfloor n2^{-i-1}\rfloor} = n\left(1-2^{-m-1}\right)+O(m)$ . On the other hand, because of the observation above, we have that $\displaystyle |\varphi(\mathbb{N}_0) \cap S_{m,n}| \le \sum_{1 \le i \le m+1}{g_i(n)}$ . But it means that $\displaystyle |\left(\mathbb{N}_0 \setminus \varphi(\mathbb{N}_0)\right) \cap [1,n]| \ge |S_{m,n}| - \sum_{1 \le i \le m+1}{g_i(n)}$ , or equivalently $\displaystyle f(n) \le O(n2^{-m-1})+O(m)-\sum_{1 \le i \le m+1}{g_i(n)}$ .(*)

Let show now by PMI that $\displaystyle g_i(n)<h\frac{n(\ln{\ln{n}}+k)^{i-1}}{(i-1)!\ln{n}}$ for some constants $k \text{ and }h$ fixed. For $i=1$ the statement is surely true (see for example well-known Chebychev’s result about $g_1(\cdot):=\pi(\cdot)$ ) and suppose that it is true for $i-1 \in \mathbb{N}_0$ .

(Under construction)

Leave a Comment

26/10/2009

Exponential complete residue system

Filed under: Mathematical matters — bboyjordan @ 11:05 PM

Let $n \in \mathbb{N} \setminus \{0,1\}$ fixed, and define $\{\sigma(1),\sigma(2),\ldots,\sigma(n)\}$ a permutation of $\{1,2,\ldots,n\}$ such that also $\{1^{\sigma(1)},2^{\sigma(2)},\ldots,n^{\sigma(n)}\}$ is a permutation of $\{1,2,\ldots,n\}$ in $\mathbb{Z}/n\mathbb{Z}$ . Then $n \in \mathbb{P} \cup 2\mathbb{P}$ . (Nguyen Tho Tung)

Solution. There are exactly $n\text{rad}(n)^{-1}-1$ numbers multiple of $\text{rad}(n)$ and strictly less of $n$ in the set $\{1,2,\ldots,n\}$ . So $(x,y) \in \mathbb{Z}^2$ exist such that $0<y<n\text{rad}(n)^{-1}$ , $x \ge n\text{rad}(n)^{-1}-1 \text{ and } n \nmid y\text{rad}(n)^x$ since $n \mid n^z$ for all $z \in \mathbb{N}_0$ . But it implies that $n \nmid \text{rad}(n)^{n\text{rad}(n)^{-1}-1}$ : that is, if a prime $p \in \mathbb{P}$ divides $n$ then $\upsilon_p(n) \ge p^{\upsilon_p(n)-1}-1$ , and at least one of the $\omega(n)$ inequalities is strict. It mean that $\upsilon_2(n) \le 3, \upsilon_3(n) \le 2 \text{ and } \upsilon_p(n) \le 1$ for all $p \in \mathbb{P} \setminus\{2,3\}$ . Now let $f(n)$ the number of quadratic residues in the set $\{1,2,\ldots,n\}$ , where also $0$ is considered a quadratic residue. Since there are exactly $\lfloor n2^{-1} \rfloor$ even integers in the set $\{1,2,\ldots,n\}$ , then $f(n) \ge \lfloor n2^{-1} \rfloor$ . It is easy to see by Chinese Therem Remainder that if $n=2^a \cdot 3^b \cdot \prod_{3 < p \mid n}{p}$ for some integer $a \le 3 \text{ and } b \le 2$ then $f(n)=f(2^a)f(3^b)\prod_{3 < p \mid n}{(p+1)2^{-1}}$ . But $f(2)=1,f(3)=\frac{2}{3}$ , $f(4)=\frac{1}{2}$ and $\max\{f(8),f(9)\}<\frac{1}{2}$ . Then the inequality $f(n) \ge \lfloor n2^{-1} \rfloor$ directly implies $n \in \mathbb{P} \cup 2 \mathbb{P}$ .[]

Additional observations. If $n \in \mathbb{Z} \cap [2,7]$ a such permutation exists (see below for examples) and there exist always a even number of such ones since $\{\sigma(1),\sigma(p)\}$ can be exchanged. Suppose that $n \in \mathbb{P} \cup 2 \mathbb{P}$ and $n>6$ ; then $f(\ell p)=\ell \frac{p+1}{2}$ for all $\ell \in \{1,2\}$ and $p \in \mathbb{P} \setminus \{2\}$ . It means that if a permutation $\{1^{\sigma(1)},2^{\sigma(2)},\ldots,n^{\sigma(n)}\}$ of $\{1,2,\ldots,n\}$ exists, then the set of $\{\sigma(\text{quadratic residues})\}$ (where $0$ is considered a quadratic residue in $\mathbb{Z}/n\mathbb{Z}$ ) is sent to the same set of $\{\sigma(\text{quadratic residues})\}$ where, by force, we must have $\{\sigma(\text{quadratic residues})\}=\{2,4,6,\ldots,p-1\} \cup \{2v+1\}$ for some integer $0 \le v \le \frac{p-1}{2}$ (in the case of $2p$ it happens essentially the same thing, but with invariant parity of each set, so that we have in total $4$ disjoint cycles). Now $1^{\sigma(1)}=1$ for all $\sigma(1)\in \mathbb{Z} \cap [1,2p]$ , so if $n=p \in \mathbb{P} \setminus \{2,3\}$ then $(p-1)^{\sigma(p-1)}$ need to be $p-1$ : it means that if $p>3$ and $4 \mid p-1$ then $\sigma(p-1)$ is the unique odd in the set of $\{\sigma(\text{quadratic residues})\}$ . It means also that if $n=2p$ for some $p \in \mathbb{P} \setminus \{2,3\}$ and $4 \mid p-1$ then such permutation does not exist (since $\sigma(p-1)$ and $\sigma(2p-1)$ cannot be both odd).

Something else, in the case $n=p \in \mathbb{P}\setminus \{2,3\}$ we must have $\sigma(p) \not \in \{1,p\}$ , otherwise since exponent can be taken modulo $p-1$ then $\{\sigma(1),\ldots,\sigma(p-1)\}$ is a permutation of $\{1,2,\ldots,p-1\}$ . If $g$ is one of $\varphi(\varphi(p))$ possible primitive root in $\mathbb{Z}/p\mathbb{Z}$ , then define $j_i \in \mathbb{Z} \cap [1,p-1]$ such that $i=g^{g^{j_i}}$ for all $i \in \mathbb{Z} \cap [1,p-1]$ . Also, define $k_i \in \mathbb{Z} \cap [1,p-1]$ such that $\sigma(i)=g^{k_i}$ for all $i \in \mathbb{Z} \cap [1,p-1]$ . It means that $\{g^{g^{j_1+k_1}},g^{g^{j_2+k_2}},\ldots,g^{g^{j_{p-1}+k_{p-1}}}\}$ is a permutation of $\{1,2,\ldots,p-1\}$ , or equivalently that $\{j_1+k_1,j_2+k_2,\ldots,j_{p-1}+k_{p-1}\}$ is a permutation of $\{1,2,\ldots,p-1\}$ , where $\{j_1,\ldots,j_{p-1}\}$ and $\{k_1,\ldots,k_{p-1}\}$ are both permutation of $\{1,2,\ldots,p-1\}$ itself. But $p-1 \mid \sum_{1 \le i \le p-1}{j_i+k_i}=2\sum_{1 \le i \le p-1}{i} \implies p-1 \mid \sum_{1 \le i \le p-1}{i}=p(p-1)2^{-1}$ , then $\frac{p}{2} \in \mathbb{Z}$ , that is a contradiction for all odd primes $p$ .

Again in the case $n=p \in \mathbb{P} \setminus \{2,3\}$ , since $1^{\sigma(1)}=1$ then $(p-1)^{\sigma(p-1)}=p-1$ that holds iff $2 \nmid \sigma(p-1)$ . Now by Euler criterion we have that $x^{\frac{p-1}{2}} \in \{1,p-1\}$ in $\mathbb{F}_p$ for all integer $x$ such that $x \in \mathbb{Z} \cap [1,p)$ : so if $4 \mid p+1$ then $\frac{1}{2}(p-1)$ belongs to $\{\sigma(1),\sigma(p).\sigma(p-1)\}$ , and if $4 \mid p-1$ then $\frac{p-1}{2} \in \{\sigma(1),\sigma(p)\}$ . And for obvious reason in every case $p-1 \in \{\sigma(1),\sigma(p)\}$ holds.

Note that it works for all $n\in \mathbb{Z} \cap [2,7]$ , infact: $n=2$ works, since we can choose $\{\sigma(1),\sigma(2)\}=\{1,2\}$ , $n=3$ works, since we can choose $\{\sigma(1),\sigma(2),\sigma(3)\}=\{2,1,3\}$ , $n=4$ works, since we can choose $\{\sigma(1),\ldots,\sigma(4)\}=\{2,1,3,4\}$ , $n=5$ works, since we can choose $\{\sigma(1),\ldots,\sigma(5)\}=\{2,5,1,3,4\}$ , $n=6$ works, since we can choose $\{\sigma(1),\ldots,\sigma(6)\}=\{2,1,4,5,3,6\}$ , $n=7$ works, since we can choose $\{\sigma(1),\ldots,\sigma(7)\}=\{6,2,1,5,7,3,4\}$ , $n=8 \not \in \mathbb{P} \cup 2\mathbb{P}$ and $n=9 \not \in \mathbb{P} \cup 2\mathbb{P}$ so they don’t work, $n=10 \in 2\mathbb{P}$ , but $\frac{10}{2}=5 \in \mathbb{P}$ and $4 \mid 5-1$ so it does not work.

A note by Tho Tung Nguyen(first comment). Case $n=p \in \mathbb{P}$ . Let $g$ one of $\varphi(\varphi(p))$ possibile primitive root in $\mathbb{Z}/p\mathbb{Z}$ and define $x \in \mathbb{N} \setminus \{0,1\}$ a integer such that $(p-1)x^{-1} \in \mathbb{Z}$ . The number of distinct integers $y \in \{1,2,\ldots,p\}$ such that there exist z in {1,2,..,p} that verifies $p\mid z^x-y$ is exactly $(p-1)x^{-1}+1$ . In fact, $0$ is always a $x$ -th power and if $y \neq p$ and $p \mid y-g^k$ for some $k \in \{1,2,\ldots,p-1\}$ then $p \mid z^x-g^k$ if and only if $p-1 \mid tx-k$ for some $t \in \mathbb{Z}$ . But $\text{gcd}(p-1,x)=x$ , so it holds if only if $x \mid k$ . Now, we return on the problem: assume that $\mu^2(p-1)=1$ , then there exist $q \in \mathbb{P}$ such that $q^2 \mid p-1$ . Define $S_x$ the set of all $x$ -th power in $\mathbb{Z}/p\mathbb{Z}$ . Since $|S_q|=(p-1)q^{-1}+1$ , also $\{1^{\sigma(1)},\ldots,p^{\sigma(p)}\}$ must have exactly $|S_q|$ number that are $q$ -th power. But $T_q:=\{q,2q,\ldots,(p-1)\} \subseteq \{\sigma(g^q),\sigma(2q),\ldots,\sigma(p-1),\sigma(p)\}$ , otherwise there will be a number greater of $|S_q|$ of q-th power. But it means that if $h \in S_q$ and $\sigma(h) \in T_q$ then $h \in S_{q^2}$ . It means that $|S_{q^2}| \ge |T_q|$ , that is $\frac{p-1}{q^2} +1 \ge \frac{p-1}{q}$ but $\frac{p-1}{2q}+1 \ge \frac{p-1}{q^2}+1 \ge \frac{p-1}{q}$ implies $q \ge \frac{p-1}{2}$ . Because by assumption we have $q^2 \mid p-1$ , then $p-1 \ge q^2 \ge \frac{p-1}{4}$ , that is $p \le 5$ . And in fact if $\mu^2(p-1)=1$ then $p=5$ is the unique solutions.

Additional observations (continue). Again about the case $n=p \in \mathbb{P}$ . We’ll show that $p=2q+1$ for some $q \in \mathbb{P}$ . Note that $\omega(p-1) \ge 2$ for all prime $p \ge 5$ , so it is enough to suppose by absurd that $\omega(p-1)$ is greater than $2$ . By the previous note we know that $\mu^2(p-1)=1$ , so it implies that $\mu^2((p-1)w^{-1})=1$ for all $w \in \mathbb{P}$ such that $w \mid p-1$ . Define $S_x$ the set of all x-th power in $\mathbb{Z}/p\mathbb{Z}$ , as before, and $R_x:=\{\sigma(i):i \in S_x\}$ .Define also $T_x$ the subset of all multiple of $x$ in $\{1,2,\ldots,p-1\}$ . It is clear that if a prime $w$ divides $p-1$ then we have that $T_w$ is a subset of $R_w$ . But $|R_w|-|T_w|=1$ , so once $\sigma(p)$ is fixed, there must exist a integer $m$ such that $m \mid p-1$ and it is one of two smallest divisor with $\omega(p-1)-1$ factors, and $T_m=R_m$ . It means that $\{ g^m ,g^{2m}\ldots,g^{p-1}\}$ is a permutation of the set $\{g^{i\sigma (i) m^2}\}_{1 \le i \le (p-1)m^{-1}}$ in $\mathbb{Z}/p\mathbb{Z}$ . It is true if and only if $\{\sigma(i)m^2\}_{1 \le i \le (p-1)m^{-1}}$ is a permutation of $\{m,2m,\ldots,p-1\}$ in $\mathbb{Z}/(p-1)\mathbb{Z}$ . And this is true if and only if $\{m\sigma(1),\ldots,m(\frac{p-1}{m})\sigma(\frac{p-1}{m})\}$ is a permutation of $\{1,2,\ldots,(p-1)m^{-1}\}$ in $\mathbb{Z}/\frac{p-1}{m}\mathbb{Z}$ . Now $\text{gcd}(m,(p-1)m^{-1})=1$ and $(p-1)m^{-1} \in \mathbb{P} \setminus \{2\}$ , and if it is really a permutation, then also the product of all elements must be the same. But by force $\sigma(0)=0$ and the product of the first set is $m^{(p-1)m^{-1}-1} ((p-1)m^{-1}-1)!^2$ that is $1$ in $\mathbb{Z}/\frac{p-1}{m}\mathbb{Z}$ and the product of the last set $((p-1)m^{-1}-1)!$ that is $-1$ in $\mathbb{Z}/\frac{p-1}{m}\mathbb{Z}$ , contradiction.

By finishing the case $n=p \in \mathbb{P}$ we’ll show that the necessary condition that $\frac{p-1}{2}=q \in \mathbb{P}$ is a Sophie Germain prime is also sufficient. In fact, it is enough to construct such a permutation $\{\sigma(1),\sigma(2),\ldots,\sigma(p)\}$ . Set $\sigma(1)=2q,\sigma(p-1)=q\text{ and }\sigma(p)=q+1$ and define $N$ the set of non quadratic residues without $2q$ and $Q$ the set of quadratic residues without $1$ and $p$ . Define also $O$ the subset of all odd numbers in $\{1,2,\ldots,p\}$ without $q$ and $2q-1$ , and $E$ the subset of all even numbers in $\{1,2,\ldots,p\}$ without $q+1$ and $2q$ and adding $2q-1$. We need to search two permutation of sets $O$ and $E$ such that every exponent of $N$ is chosen in $O$ and it is again a permutation of $N$ , and every exponent of $Q$ is chosen in $E$ and it is again a permutation of $Q$ . Evidently, if $s$ is a odd generators of $\mathbb{Z}/2q\mathbb{Z}$ then the set $N$ can be represented as $\{g^{s^i}\}$ where $i \in \mathbb{Z} \cap [0,q-2]$ . And the set $O$ can be represented as $\{s^i\}$ where $i \in \{0,0,1,2,\ldots,\frac{q-1}{2},\frac{q+3}{2},\ldots,q-2\}$ . It is obvious that we need to work in $\varphi(\varphi(p))=q-1$ : now if a element that belongs to $N$ can be represented by $g^{s^j}$ for some $j \in \mathbb{Z} \cap [0,\frac{q-3}{2}]$ then set $\sigma(g^{2^j})=s^j$ . Otherwise (i.e. it can be represented as $g^{s^j}$ for some $j \in \mathbb{Z} \cap [\frac{q-1}{2},q-2]$ ) set $\sigma(g^{s^j})=s^{j+1}$ . It can be easily seen that the image of $N$ is really a permutation of $N$ . The same work can be done with the set $Q$ . In fact $Q$ can be reprented as $\{g^{t^i}\}$ where $t$ is a even generator in $\mathbb{Z}/2q\mathbb{Z}$ and $i \in \mathbb{Z} \cap [0,q-2]$ and the set $E$ as $\{t^i\}$ where $i \in \{1,2,\ldots,\frac{q-1}{2},\frac{q-1}{2},\ldots,q-2\}$ . And set $\sigma(0)=q-2$ and $\sigma(g^{t^j})=t^j$ if $j \in \mathbb{Z} \cap [1,\frac{q-1}{2}]$ , and $\sigma(g^{t^j})=t^{j-1}$ if $j \in \mathbb{Z} \cap [\frac{q+1}{2},q-2]$ . Also this time it can be easily seen that the image of $Q$ is really a permutation of $Q$ in $\mathbb{Z}/p\mathbb{Z}$ .

We are lead now to the only remaining case $n=2p \in 2\mathbb{P}$ for some $p \ge 7$ . The note of Tho Tung Nguyen can be directly extended to this case, and working in the set $\{1,2,\ldots,2p\}$ we have that if $q^2 \mid p-1$ for some prime $q$ then $2(1+(p-1)q^{-2})=|S_{q^2}| \ge |T_q|=2(p-1)q^{-1}$ , that is $p \le 5$ , as before. So, if $n=2p \in 2\mathbb{P}$ then $|\mu(p-1)|=1$ .

But next observation about $\omega(p-1)$ cannot be applied since the presence of a double residue system modulo $p$ will square the residue from which we have obtained the contradiction. Any help would be appreciated (it can also be that the condition $|\mu(p-1)|=1$ is necessary and sufficient, but I don’t have a proof of it..)

Comments (21)

09/10/2009

Numbers as sum of two odd primes

Filed under: Mathematical matters — bboyjordan @ 1:01 AM

This time we’ll prove that for every integer $k \in \mathbb{N}_0$ there exist infinitely many positive integer $x$ which can be written in more than $k$ ways as sum of two odd primes.

As almost proofs about prime numbers, we’ll show assuming the contrary, i.e. the sequence $\{y_i\}_{i \in \mathbb{N}_0}$ is bounded by some real constant $\ell>0$ , where $y_i$ is defined as the number of ways that the number $2i$ is representable as sum of two odd primes.
Obviusly $y_i$ represents the coefficient of $x^{2i}$ in the infinite serie $p^2(x)$ , where $\displaystyle p(x):=\sum_{p \in \mathbb{P} \setminus \{2\}}{x^p}$ .

Assuming that $x$ is a random variable in $(0,1)$ , we can say that the inequality $\displaystyle p^2(x) \le \ell \frac{x^4}{1-x^2}$ holds, where we have used the well-known identity $\displaystyle \sum_{i \in \mathbb{N}}{z^i}=(1-z)^{-1}$ for every $z \in (-1,1)$ .

It follows that $\displaystyle \sum_{p \in \mathbb{P}\setminus\{2\}}{x^{p-1}} \le x\sqrt{\frac{\ell}{1-x^2}}$ holds. So it is also true that $\displaystyle \int_0^1{\sum_{p \in \mathbb{P}\setminus\{2\}}{x^{p-1}} } \le \ell^{\frac{1}{2}} \int_0^1{\frac{x}{\sqrt{1-x^2}}}$ .

It means that $\displaystyle \left(\sum_{p \in \mathbb{P}\setminus\{2\}}{p^{-1}}\right)^2 \le \ell$ , so it is enough to prove that the well-known serie $\displaystyle \sum_{p \in \mathbb{P}}{\frac{1}{p}}$ diverges to get a contradiction (note that we can substitute in the text of the problem the sequence of primes with a general sequence of positive integers $\{a_i\}_{i \in \mathbb{N}}$ such that $\displaystyle \sum_{i \in \mathbb{N}}{a_i^{-1}}$ diverges). (*)

We’ll use now the well-known Euler product: it states that if $f(\cdot):\mathbb{N}_0 \to \mathbb{C}$ is a multiplicative aritmetical function such that $\displaystyle \sum_{n \in \mathbb{N}}{f(n)}$ is absolutely convergent, then the identity $\displaystyle \sum_{n \in \mathbb{N}}{f(n)}=\prod_{p \in \mathbb{P}}{\sum_{i \in \mathbb{N}}{f(p^i)}}$ holds. We have $f(1)=1$ since $f(n)=f(1)f(n)$ for all $n \in \mathbb{N}_0$ , and $f(\cdot)$ is not null everywhere by the definition of aritmetical function. Define $\displaystyle R:=\sum_{n \in \mathbb{N}}{f(n)}$ and $\displaystyle P(x):=\prod_{x\ge p \in \mathbb{P}}{\sum_{i \in \mathbb{N}}{f(p^i)}}$ and $\displaystyle Q(x):=\{n \in \mathbb{N}_0: \upsilon_p(n)>0 \implies x \le p \text{ for all }p \in \mathbb{P}\}$ , for every real $x>0$ fixed.

It is clear that if a positive integer $y \not \in Q(x)$ then $y>x$ , and it means that $\displaystyle |R-P(x)|=|\sum_{n \not \in Q(x)}{f(n)}| \le \sum_{n \not \in Q(x)}{|f(n)|} \le \sum_{n >x }{|f(n)|}$ .

The statement follows taking the limit $x \to +\infty$ , in fact the product $\displaystyle \prod_{p \in \mathbb{P}}{\sum_{i \in \mathbb{N}}{f(p^i)}}$ converges absolutely since $\displaystyle \left|\sum_{i \in \mathbb{N}_0}{f(p^i)}\right| \le \sum_{i \in \mathbb{N}_0}{|f(p^i)|} \le \sum_{n \in \mathbb{N}_0}{|f(n)|}$ , that converges by assumption. So we have shown that $R-P(x)=o(1)$ , taking in mind the additive stucture of $\mathbb{N}$ . In particular if $f(\cdot)$ is a completely multiplicative function then $\displaystyle \sum_{n \in \mathbb{N}}{f(n)}= \prod_{p \in \mathbb{P}}{ \left( 1-f(p)\right)^{-1}}$ .

Assuming the above notation, it is clear that $\displaystyle \prod_{x \le p \in \mathbb{P}}{ \left( 1-p^{-1} \right) ^{-1}} = \sum_{i \in Q(x)}{i^{-1}} \ge \sum_{1 \le i \le n}{i^{-1}}$ . (**)

It can be useful also to know the Abel partial summation. Let $\displaystyle \{a_i\}_{i \in \mathbb{N}}$ a divergent and strictly increasing sequence of positive real numbers and let $\displaystyle \{\gamma_i\}_{i \in \mathbb{N}}$ a sequence of complex numbers. Define $\displaystyle \varphi(\cdot):\mathbb{R}^+ \to \mathbb{C}$ a arbitrary function and $\displaystyle A(x):= \sum_{\gamma_n \le x}{a_n}$ , for every real $x>0$ fixed. Then $\displaystyle \sum_{1 \le n \le N}{a_n\varphi(\gamma_n)}= \sum_{1 \le n \le N}{[A(\gamma_n)-A(\gamma_{n-1}]\varphi(\gamma_n)} = A(\gamma_N)\varphi(\gamma_N)-\sum_{1 \le n \le N-1}{A(\gamma_n)\left(\varphi(\gamma_{n+1})-\varphi(\gamma_n)\right)}$ .

In particular, if $\varphi(\cdot) \in C^1(\mathbb{R}^+)$ (so it is continous and derivable), and $x \ge \gamma_1$ and $\displaystyle N:=\max\{n \in \mathbb{N}_0:\gamma_n \le x\}$ , then $A(\cdot)$ is constant in $[\gamma_n,\gamma_{n+1})$ and in $[\gamma_N,x)$ , so we can say that:
$\displaystyle \displaystyle \sum_{1 \le n \le N}{a_n\varphi(\gamma_n)} =\left(A(x)\varphi(x)-\int_{\gamma_N}^x{A(t)\varphi'(t)dt}\right)-$ $\displaystyle \left( \sum_{1 \le n \le N-1}{\int_{\gamma_n}^{\gamma_{n+1}}{A(t)\varphi'(t)dt}}\right)$ $\displaystyle = A(x)\varphi(x)-\int_{\gamma_1}^x{A(t)\varphi'(t)dt}$ .

Now, if $a_i:=1, \gamma_i:=i$ for all $i \in \mathbb{N}_0$ and $\varphi(x)=x^{-1}$ for all $x \in \mathbb{R}^+$ , then $\displaystyle \sum_{i \le x}{i^{-1}}= \sum_{\gamma_n \le x}{a_n \varphi(\gamma_n)}= A(x)\varphi(x) - \int_1^{x}{\frac{\lfloor t \rfloor}{-t^2}dt}$ $\displaystyle =\frac{\lfloor x \rfloor}{x}+\ln(x)-\int_1^{x}{\frac{ \{t\}}{t^2}dt} = \frac{\lfloor x \rfloor}{x}+\ln(x)-\int_1^{+\infty}{\frac{ \{t\}}{t^2}dt}+O\left(\int_x^{+\infty}{\frac{ \{t\}}{t^2}dt}\right)$ $=\ln(x)+\gamma+O(x^{-1})$ , where $\displaystyle \gamma:=1-\int_1^{+\infty}{\frac{ \{t\}}{t^2}dt}$ is the well-known Eulero Mascheroni constant.

Turning at (*) and noting that $\displaystyle -\ln(1-z)=z+O(z^2)$ for all $z \in [0,\frac{1}{2}]$ , we can conclude with:
$\displaystyle \sum_{x \ge p \in \mathbb{P}}{p^{-1}}=-\sum_{x \ge p \in \mathbb{P}}{\ln\left(1-p^{-1}\right)}+O\left(\sum_{x \ge p \in \mathbb{P}}{p^{-2}}\right)$ $\displaystyle = \ln\left(\prod_{x \ge p \in \mathbb{P}}{(1-p^{-1})^{-1}} \right) + O(1) \ge \ln(\ln(x))+O(1)$ , that is clearly unbounded.[]

We can note finally that we have shown a strong quantitative lower bound on $\displaystyle \sum_{x \ge p \in \mathbb{P}}{p^{-1}}$ , in fact the famous Mertens formula for prime numbers states that exist a fixed $k \in \mathbb{R}$ such that for all $x$ sufficiently large we have $\displaystyle \sum_{x \ge p \in \mathbb{P}}{p^{-1}}=\ln(\ln(x))+k+O\left((\ln x)^{-1}\right)$ .

We remember that first, second and third Mertens formula states respectively that: $\displaystyle \sum_{x \ge n \in \mathbb{N}_0}{\Delta(n)n^{-1}} =\sum_{x \ge p \in \mathbb{P}}{\ln(p)p^{-1}}=\int_1^x{\psi(t)t^{-2}dt}=\ln(x)+O(1)$ (with the usual notation) and the formula of primes, useful in the proof of Prime Number Theorem, can be obtained with the Abel partial summation directly on the second one, but it can be found in all number theory book.

Leave a Comment

Bboyjordan's Blog

19/12/2011

List of funny problems (3rd)

05/03/2011

Fundamental theorem of Asset Pricing

02/03/2011

Elementary cases of Mihailescu Theorem

25/07/2010

List of funny problems (2nd)

04/11/2009

f(n)<f(n+1)<f(n+2) for infinitely many n

A list of own problems

31/10/2009

A list of funny problems

30/10/2009

Arbitrary large gap in the image of Euler function

26/10/2009

Exponential complete residue system

09/10/2009

Numbers as sum of two odd primes

Blogroll

Follow “Bboyjordan's Blog”