Home » Posts tagged 'Number Theory'

Tag Archives: Number Theory

On the factorial

Let \mu denote the Möbius function and \left \lfloor \cdot \right \rfloor denote the floor function. Prove that:

    \[n! = \prod_{j=1}^{\infty} \prod_{i=1}^{\infty} \left ( \left \lfloor \frac{n}{ij} \right \rfloor! \right )^{\mu(i)}\]

Solution

The RHS equals

    \begin{align*} \prod_{j=1}^{\infty} \prod_{i=1}^{\infty} \left ( \left \lfloor \frac{n}{ij} \right \rfloor! \right )^{\mu(i)} &= \prod_{k=1}^n \prod_{i|k} \left( \left \lfloor \frac{n}{k}\right\rfloor!\right)^{\mu(i)} \\ &= \prod_{k=1}^n \left( \left \lfloor \frac{n}{k}\right\rfloor!\right)^{\sum_{i|k}\mu(i)} \\ &= n! \end{align*}

since \sum \limits_{i | k} \mu(i) = 0 for k>1.

Read more

Proof of “Fermat’s last theorem”

Let x,y,z,n\in \mathbb{N}^* and n \geq z. Prove that the equation

    \[x^n+y^n=z^n\]

has no solution.

Solution

Without loss of generality , assume that x<y. If x^n+y^n=z^n held , then it would be z^n > y^n thus z^n \geq (y+1)^n. It follows from Bernoulli’s inequality that,

    \begin{align*} z^n &=x^n +y^n\\ &< 2y^n \\ &\leq \left(1 + \frac {n}{z} \right) y^n \\ &\leq \left(1 + \frac {1}{z} \right)^ny^n\\ &< \left(1 + \frac {1}{y} \right)^ny^n \\ &= (y+1)^n \\ &\leq z^n \end{align*}

which is an obscurity. The result follows.

Read more

Eulerian equality

We know that there are infinite Pythagorian triplets, that is numbers a, b, c such that

(1)   \begin{equation*} a^2 = b^2 +c^2 \end{equation*}

Let us investigate if there exist triplets such that

(2)   \begin{equation*} \varphi \left( a^2 \right) = \varphi \left( b^2 \right) + \varphi \left( c^2 \right) \end{equation*}

where \varphi denotes the Euler’s totient function.

Solution

Indeed, there are infinite triplets such that (2) is satisfied. For example noticing that

    \[\varphi \left(4^2 \right) + \varphi \left(6^2 \right) = 8 + 12 = 20 = \varphi \left(5^2 \right)\]

we deduce that for each natural N such that (N, 30) =1 we have

    \[\varphi \left((4N)^2 \right) + \varphi \left((6N)^2 \right) = 20\varphi \left(N^2\right) = \varphi \left((5N)^2 \right)\]

Read more

Square of an integer

Let a, b be positive integers such that ab +1 divides a^2+b^2. Show that

    \[\frac{a^2+b^2}{ab+1}\]

is the square of an integer.

Solution

This is a very well known problem. It first appeared in IMO 1988 held in Canberra, Australia. It even has its own Wikipedia page.

History Background

One of the organisers had sent this exercise to all professors of Number Theory to check if the exercise is original and try to solve it within 4 hours. No one was able to do so. However, one Bulgarian student managed to solve the problem in less than 4 hours ( his solution was fallen from the sky )  and for that he was awarded a special reward beyond the medal.

Solution

 

Choose integers a,b,k such that a^2+b^2=k(ab+1) Now, for fixed k, out of all pairs (a,b) choose the one with the lowest value of \min(a,b). Label b'=\min(a,b), a'=\max(a,b). Thus, a'^2-kb'a'+b'^2-k=0 is a quadratic in a'. Should there be another root, c', the root would satisfy: b'c'\leq a'c'=b'^2-k<b'^2\implies c'<b' Thus, c' isn’t a positive integer (if it were, it would contradict the minimality condition). But c'=kb'-a', so c' is an integer; hence, c'\leq 0. In addition, (a'+1)(c'+1)=a'c'+a'+c'+1=b'^2-k+b'k+1=b'^2+(b'-1)k+1\geq 1 so that c'>-1. We conclude that c'=0 so that b'^2=k.

This construction works whenever there exists a solution (a,b) for a fixed k, hence k is always a perfect square.

Read more

On permutation

Let x_1, x_2, \dots, x_k be vectors of m – dimensional Euclidean space such that x_1+x_2+\cdots+x_k=0. Prove that there exists a permutation \pi of the integers \{1, 2, \dots,k\} such that

    \[\left \| \sum_{i=1}^{n} x_{\pi(i)} \right \|\leq\left ( \sum_{i=1}^{k} \left \| x_i \right \|^2 \right )^{1/2}\]

for each n=1,2, \dots, k.

Solution

We define \pi inductively. Set \pi(1)=1.Assume \pi is defined for i=1, 2, \dots, n and also

(1)   \begin{equation*} \left \| \sum_{i=1}^{n} x_{\pi(i)} \right \|^2 \leq \sum_{i=1}^{n} \left \| x_{\pi(i)} \right \|^2 \end{equation*}

Note that (1) is true for n=1. We choose \pi(n+1) in a way that (1) is fulfilled for n+1 instead of n. Set y=\sum \limits_{i=1}^{n} x_{\pi(i)} and A=\{1,2, \dots, k\} \setminus \{\pi(i) : i=1,2, \dots, n\}. Assume that (y, x_r)>0 for all r \in A.  Then \left ( y , \sum \limits_{r \in A} x_r \right )>0 and in view of y + \sum \limits_{r \in A} x_r =0 ones gets -(y, y)>0 which is impossible. Hence , there is r\in A such that

(2)   \begin{equation*} (y, x_r)\leq 0\end{equation*}

Put \pi(n+1) = r . Then using (2) and (1) we have

    \begin{align*} \left \| \sum_{i=1}^{n+1} x_{\pi(i)} \right \|^2 &= \left \| y + x_r \right \|^2 \\ &=\left \| y \right \|^2 + 2\left ( y, x_r \right ) + \left \| x_r \right \|^2 \\ &\leq \left \| y \right \|^2 + \left \| x_r \right \|^2 \\ &\leq \sum_{i=1}^{n} \left \| x_{\pi(i)} \right \|^2 + \left \| x_r \right \|^2\\ &= \sum_{i=1}^{n+1} \left \| x_{\pi(i)} \right \|^2 \end{align*}

which verifies (1) for n+1. Thus we define \pi for every n=1, 2, \dots, k. Finally from (1) we get

    \[\left \| \sum_{i=1}^{n} x_{\pi(i)} \right \|^2 \leq \sum_{i=1}^{n} \left \| x_{\pi(i)} \right \|^2 \leq \sum_{i=1}^{k} \left \| x_i \right \|^2\]

Read more

Who is Tolaso?

Find out more at his Encyclopedia Page.

Donate to Tolaso Network