Bboyjordan's Blog

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.

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\}$ . []

Leave a Comment

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)

13/10/2009

Fundamental theorem of asset pricing

Filed under: Also a bit of economy — bboyjordan @ 1:45 AM

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.

A model of a financial market is defined as an $\mathbb{R}^{d+1}$ -valued stochastic process $S=(S_t)_{0 \le t \le T}=(S_t^0,S_t^1,\ldots,S_t^d)_{0 \le t \le T}$ , adapted to the filtered stochastic base $(\Omega,\text{F},(\text{F}_t)_{0 \le t \le T},P)$ , where $(d,T) \in \mathbb{N}_0^2$ is fixed, $t$ is a integer variable: an economic agent is able to buy and sell financial assets, so that the decision taken at $t \in \mathbb{N} \cap [1,T]$ can only use information available at time $t$ , which is modelled by the $\sigma$ -algebra $\text{F}_t$ .
A trading strategy, instead, is an $\mathbb{R}^{d+1}$ -valued process $H=(H_t)_{0 \le t \le T}$ which is predictable (i.e. $H_t$ is $\text{F}_{t-1}$ -measureable for all $t \in \mathbb{N} \cap [1,T]$ ). The value of the portafolio at time $t$ is intuitively defined as $V_t:=(H_t,S_t)$ , where $(\cdot,\cdot)$ denotes the usual inner product.

Beginning with the assumption of a finite probability space (i.e. there exist $N \in \mathbb{N}_0$ such that $\Omega:=\{\omega_1,\omega_2,\ldots,\omega_N\}$ ) equipped with a probability measure $P$ such that $P(\omega_n):=p_n \in (0,1]$ for all $n \in \mathbb{N} \cap [1,N]$ , we can assume that $\text{F}=\text{F}_T=2^{\Omega}$ and that the increasing sequence of $\sigma$ -algebras $\text{F}_0 \subseteq \text{F}_1 \subseteq \ldots$ does not necessary start with the trivial one $\{0,\Omega\}$ .
We’ll assume also that the predictable trading strategy is self financing: it means that $(H_t,S_t)=(H_{t+1},S_t)$ for all $t \in \mathbb{N} \cap [1,T)$ , and it trivially implies that the final value $V_T$ of the hypotetical portfolio is $V_0+\displaystyle \sum_{1 \le t \le T}{(H_t,\Delta S_t)}$ , that is $V_0+(H \cdot S)_T$ in notation of stochastic integration. Defined $\mathfrak{H}$ the set of all possible self financing trading strategies, we have obviusly that for all $\alpha \in \mathbb{R}$ the set of contingent claims attainable at price $x$ is given by $K_{\alpha}:=\{x+(H\cdot S)_T : H \in \mathfrak{H}\}$ , that is a subspace of $\mathbb{R}^N$ (a realization for each world state). Define also $C_{\alpha} \subseteq \mathbb{R}^n$ the set of contingent claims super-replicable at price $\alpha \in \mathbb{R}$ the convex cone $C_{\alpha}:=\{y \in \mathbb{R}^N: \exists x \in K_{\alpha} \text{ with } x \ge y\}$ . Again, a measure $Q$ on $(\Omega,\text{F})$ is called an equivalent martingale measure for $S$ if $Q$ have the same sets of null measure of $P$ and $S$ is a martingale under $Q$ (i.e. $\mathbb{E}_Q[S_{t+1}|\text{F}_t]=S_t$ for all $t \in \mathbb{N} \cap [1,T)$ ).

By definition, a financial maket $S$ satisfies no-arbitrage condition (NA) if $K_0 \cap \mathbb{R}^N_+=\{0\}$ , if and only if $C_0 \cap \mathbb{R}^N_+=\{0\}$ , where $\mathbb{R}^N_+$ denotes the non-negative othant of $\mathbb{R}^N$ and $0 \in \mathbb{R}^N$ is the zero vector.

Lemma 1. If the financial market $S$ satisfies (NA) then $C_0 \cap (-C_0) = K_0$ .
On one hand the relation $K_0 \subseteq C_0 \cap (-C_0)$ is trivial by definition; on the other hand, if $h \in \mathbb{R}^N$ verifies $h \in C_0 \cap (-C_0)$ , then there exist $(a_1,a_2,b_1,b_2) \in K_0^2 \times \mathbb{R}^N_+$ such that $h=a_1+b_1=a_2-b_2$ . Since $K_0$ is a subspace of $\mathbb{R}^N$ then $a_1-a_2 \in K_0$ : it follows that $a_1-a_2=b_1+b_2 \in K_0 \cap \mathbb{R}^N_+$ , that is $\{0\}$ since the financial maket $S$ satisfies (NA). But then $a_1=a_2$ and $b_1+b_2=0$ , so $h=a_1=a_2 \in K_0$ , that is $C_0 \cap (-C_0) \subseteq K_0$ .

Lemma 2. A probability measure $Q$ on $(\Omega,\text{F})$ is a equivalent martingale measure for $S$ if and only if $\mathbb{E}_Q[f]=0$ for all $f \in K_0$ , or equivalently $\mathbb{E}_Q[g] \le 0$ for all $g \in C_0$ .

The following classical form is due to M.Harrison and S.R.Pliska.
Fundamental Theorem of Asset Pricing. $M^e(S) \neq \emptyset$ if and only if $S$ satisifes (NA)

(Under costruction)

Leave a Comment

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

About number of prime divisor of a infinite sequence

Filed under: Mathematical matters — bboyjordan @ 12:49 AM

The result that we’re going to prove is due to Kobayahi and it states that if a infinite sequence of positive integer $\{a_i\}_{i \in \mathbb{N}}$ is not bounded and $\displaystyle \omega\left(\prod_{i \in \mathbb{N}}{a_i}\right)$ is finite, then $\displaystyle \omega\left(\prod_{i \in \mathbb{N}}{(a_i+k)}\right)$ is finite too if and only if $k=0$ .
(Under construction)

Leave a Comment

08/10/2009

Arbitrary long sequences with distinct omega(.)

Filed under: Mathematical matters — bboyjordan @ 2:00 AM

We’ll show that, once the integer $k >1$ is fixed, then there exist infinitely many $x \in \mathbb{N}$ such that $\displaystyle \prod_{1 \le i < j \le k}{(\omega(x+i)-\omega(x+j))^2}>0$ .
That’s not so difficult, but the idea which solves this one looks interesting, at least to me
(Under costruction)

Leave a Comment

04/11/2009

31/10/2009

30/10/2009

26/10/2009

13/10/2009

09/10/2009

08/10/2009

Blogroll