Home » Posts tagged 'Number Theory'

Tag Archives: Number Theory

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

Irreducible fraction

Find all positive integers \alpha such that it holds that

(1)   \begin{equation*} \frac{1}{\alpha} = 0.\bar{\alpha} \end{equation*}

where \overline{ \cdot } stands for the period.

Solution

Well,

    \begin{align*} \frac{1}{\alpha} = 0.\bar{\alpha} &\Leftrightarrow \frac{1}{\alpha} = 0.\alpha \alpha \alpha \dots \\ &\Leftrightarrow \frac{1}{\alpha} = \frac{\alpha}{10} \sum_{i=0}^{\infty} \frac{1}{10^i} \\ &\Leftrightarrow \frac{1}{\alpha} = \frac{\alpha}{9}\\ &\!\!\!\!\!\!\!\overset{\alpha>0}{\Leftarrow \! =\! =\! \Rightarrow } \alpha = 3 \end{align*}

Read more

Divisibility

Prove that the product of n consecutive positive integers divides n!.

Solution

The number of different combinations of N+n over N is of course an integer and equals to

    \[\begin{pmatrix} N+n\\ N \end{pmatrix} = \frac{(N+1)(N+2)...(N+n)}{n!}\]

and the result follows.

Any questions?

Read more

gcd and subgroup

Let H be a non trivial subgroup and a_1, a_2, \dots , a_n \in H. Prove that

    \[\gcd (a_1 , a_2 , \dots, a_n ) \mathbb{Z} \subseteq H\]

Solution

It is enough to prove it for the n=2 case since we can then reduce it by using the fact that

\gcd(a_1, a_2, \dots, a_n) = \gcd(a_1, a_2, \dots, a_{n-2}, \gcd(a_{n-1}, a_n))

We have that xa_1 + y a_2 \in H for any integers x and y. But by Bezout’s lemma we can find x , y such that

    \[x a_1 + y a_2 = \gcd(a_1, a_2)\]

and hence \gcd(a_1, a_2)\mathbb{Z} \subseteq H.

Read more

Donate to Tolaso Network