## Homework 5: Number Theory Problem 1 Find all positive integers \( n \) such that \( n(n+1) \) is a perfect square. Since \( n \) and \( n+1 \) are coprime numbers, if \( n(n+1) \) is a perfect square, then each of \( n \) and \( n+1 \) has to be a perfect square itself. However that is impossible since if \( n=x^2 \) and \( n+1=y^2 \) we would have \( 1=y^2-x^2=(y-x)(y+x) \) and \( 1 \) can’t be expressed as a product of two different integers. Hence there are no such integers. Problem 2 Assume that \( x \) and \( y \) are non-negative integers such that \( 15x+11y \) is divisible by \( 37 \). Prove that \( 7x+15y \) is divisible by \( 37 \). Since \( 37\mid 15x+11y \) then \( 37\mid 30x+22y \). Thus \[ 37\mid 37(x+y)-(30x+22y)=7x+15y.\] Problem 3 There are \( n \) books in a library. If books are to be arranged in boxes with \( 7 \) books in each box, then \( 5 \) books remain. If they are arranged with \( 9 \) books in each box, then \( 3 \) books remain, and if they are arranged with \( 11 \) books in each box, then \( 7 \) books remain. What is the smallest possible value for \( n \). This is Chinese remainder theorem. We need to solve the system of congruencies: \begin{eqnarray*} n&\equiv 5 &(\mbox{mod }7)\\ n&\equiv 3 &(\mbox{mod }9)\\ n&\equiv 7& (\mbox{mod }11). \end{eqnarray*} From the first two congruencies we conclude that \( n\equiv 12 \) (mod \( 63 \)). We need to find which of the numbers \( 12 \), \( 63+12 \), \( 2\cdot 63+12 \), \( \dots \), \( 10\cdot 63+12 \) is congruent to \( 7 \) modulo \( 11 \). We need to solve \( k\cdot 63+12\equiv 7 \) (mod \( 11 \)) which is equivalent to \( -3k+1\equiv 7 \) (mod \( 11 \)). The solution is \( k\equiv -2 \) (mod \( 11 \)), or \( k=9 \). Therefore the smallest such \( n \) is \( n=9\cdot 63+12=579 \). Problem 4 Assume that \( n_1 \), \( n_2 \), \( \dots \), \( n_k \) are positive integers whose greatest common divisor is equal to \( d \). Prove that there exist integers \( \alpha_1 \), \( \alpha_2 \), \( \dots \), \( \alpha_k \) such that \[ \alpha_1n_1+\alpha_2n_2+\cdots+\alpha_kn_k=d.\] We will prove the required statement using the induction on \( k \). - Case \( k=2 \):
Assume that \( a \) and \( b \) are positive integers such that \( d \) is their greatest common divisor. There exist integers \( \alpha \) and \( \beta \) such that \( d=\alpha a+\beta b \). We prove this by induction on \( m=\min\{a,b\} \). The statement is trivial for \( m=1 \). Assume it holds for all non-negative integers smaller than \( m \). Assume that \( b\leq a \) and \( b=m \). Then there exist positive integers \( p \) and \( q \) such that \( q\in\{0,1,\dots, b-1\} \) and \( a=bp+q \). The greatest common divisors of \( b \) and \( q \) is equal to \( d \). If \( q=0 \) then we have \( b\mid a \) and \( d=b \). We can clearly write \( d=0a+1b \). Assume that \( q\neq 0 \). Applying inductional hypothesis for the pair \( (b,q) \) we have that there are integers \( \beta^{\prime} \) and \( \alpha \) such that \( d=\beta^{\prime} b+ \alpha q \). We now have \( d=\beta^{\prime} b+\alpha (a-bp)=\alpha a+(\beta^{\prime}-p)b \) and we may take \( \beta=\beta^{\prime}-p \). - Assume that the statement holds for some positive integer \( k \). We will now prove it for \( k+1 \).
Let \( d^{\prime} \) be the greatest common divisor of \( n_1 \), \( n_2 \), \( \dots \), \( n_k \). Then \( d \) is the greatest common divisor of \( d^{\prime} \) and \( n_{k+1} \) hence there are \( \alpha \), \( \alpha_{k+1}\in\mathbb Z \) such that \( \alpha d^{\prime}+\alpha_{k+1} n_{k+1}=d \). By the inductional hypothesis there are integers \( \alpha^{\prime}_1 \), \( \dots \), \( \alpha^{\prime}_{k} \) such that \( \alpha_1 n_1+\cdots + \alpha_k n_k=d^{\prime} \). Therefore \[ d=\alpha d^{\prime}+\alpha_{k+1} n_{k+1}= \alpha\alpha^{\prime}_1n_1+\cdots+ \alpha\alpha^{\prime}_k n_k+\alpha_{k+1}n_{k+1},\] and the statement holds for \( (\alpha_1,\dots, \alpha_k,\alpha_{k+1})=(\alpha\alpha^{\prime}_1,\dots,\alpha\alpha^{\prime}_k,\alpha_{k+1}) \).
Problem 5 Let \( n\geq 3 \) be an odd integer. Prove that every integer \( l \) satisfying \( 1\leq l\leq n \) can be represented as a sum or difference of two integers each of which is less than \( n \) and relatively prime to \( n \). Let \( n=p_1^{\alpha_1}\cdots p_k^{\alpha_k} \), where \( p_1,\dots, p_k \) are prime numbers and \( \alpha_1, \dots \alpha_k \) positive integers. Assume that \( l \) is given and that \( l\equiv t_i\;(\mbox{mod }p_i) \). Since \( p_i> 2 \) we can choose \( s_i \) such that \( s_i\not\equiv 0\;(\mbox{mod }p_i) \) and \( s_i\not \equiv t_i\;(\mbox{mod }p_i) \). By the Chinese Remainder Theorem there exists an integer \( s< p_1\dots p_k \) such that \( s\equiv s_i\;(\mbox{mod }p_i) \) for every \( i=1,\dots, k \). If \( s< l \) then choose \( a=s \) and \( b=l-s \). If \( s> l \) then we can choose \( a=s \) and \( b=s-l \). It is easy to verify that such \( a \) and \( b \) satisfy the conditions of the problem. Problem 6 Prove that there is no positive integer \( n \) for which \( n^5 \) can be written as a product of six consecutive positive integers. It is easy to show that at least one of \( 6 \) consecutive numbers is relatively prime to each of the others (\( 3 \) of these numbers are odd, exactly one of these odd numbers is divisible by \( 3 \), and for each prime \( p> 3 \) at most one is divisible by \( p \)). Assume that \( x-2, x-1, x, x+1, x+2, x+3 \), \( x\geq 3 \) are given numbers. The number relatively prime to the others has to be a perfect \( 5 \)th power. Let \( F \) be the product of the other \( 5 \) numbers. We have: \[ P(x)=(x-2)(x-1)x(x+1)(x+2)=x^5-5x^3+4x \leq F\leq x^5+5x^4+5x^3-5x^2-6x = (x-1)x(x+1)(x+2)(x+3)=Q(x).\] Since for \( x\geq 3 \) we have \( (x+1)^5> Q(x)\geq F\geq P(x)> (x-1)^5 \) we conclude that \( F=x^5 \). However this is a contradiction since \( x \) is relatively prime to \( x-1 \) and \( x+1 \) and at least one of these numbers is a factor of \( F \). Problem 7 Let \( n\geq 5 \) be a natural number. Prove that the following two statements are equivalent: **(a)**Neither of the numbers \( n \) and \( n+1 \) is prime.**(b)**The closest integer to \( \displaystyle\frac{(n-1)!}{n^2+n} \) is even.
Let us denote \( \displaystyle f(n)=\frac{(n-1)!}{n^2+n} \). - (a)\( \Rightarrow \)(b):
In this case \( f(n) \) is an integer. We only need to show that it is even. Notice first that in this case we must have \( n\geq 8 \). Since \( n \) and \( n+1 \) are composite and relatively prime there are distinct integers \( a \), \( b \), \( c \), \( d \) all smaller than \( n-1 \) such that \( n=ab \) and \( n+1=cd \). Since only one of \( n \) and \( n+1 \) is even, at most two of the numbers \( a \), \( b \), \( c \), \( d \) is even. Therefore there is an even number in \( \{1,2,\dots, n-1\}\setminus\{a,b,c,d\} \) hence \( \displaystyle f(n)=\frac{(n-1)!}{abcd} \) is even. - (b)\( \Rightarrow \)(a):
Assume that one of \( n \) and \( n+1 \) is prime. We will prove that the closest number to \( f(n) \) is odd. We will consider two cases based on whether \( n \) or \( n+1 \) is prime.**Case 1:**\( n=p \) for some prime number \( p \). According to Wilson’s theorem we have that \( (p-1)!\equiv -1 \) (mod \( p \)). The number \( p+1 \) is composite (since it is even) hence there exists an integer \( A \) such that \( (p-1)!= A\cdot (p+1) \). Let us prove that the number \( A \) must be even. The set \( \{1,2,\dots, p-1\} \) contains at least two even integers since \( p\geq 5 \). Let \( k \) be the largest integer such that \( 2^k\mid p+1 \). Then the set \( \{1,2,\dots, p-1\}\setminus \left\{2^k,\frac{p+1}{2^k}\right\} \) contains at least one even integer unless \( p+1=2^k \). If the latter is the case then the set \( \{1,2,\dots, p-1\}\setminus\{2,2^{k-1}\} \) contains number 6 which is even.Since \( p+1\equiv 1 \) (mod \( p \)) we conclude that \( A\equiv -1 \) (mod \( p \)) and there is an odd integer \( m \) such that \( A=mp-1 \). We now have \[ f(n)=\frac{(mp-1)(p+1)}{p(p+1)}=\frac{mp-1}{p}=m-\frac1p.\] Clearly, the closest integer to \( f(n) \) is \( m \) which is odd. **Case 2:**\( n+1=p \) for some prime number \( p \). We now have \( \displaystyle f(n)=\frac{(p-2)!}{(p-1)\cdot p}=\frac{(p-1)!}{(p-1)^2\cdot p} \). Using a method very similar to the one used in the previous case we can prove that \( \frac{(p-2)!}{p-1} \) is even. Since \( (p-1)^2\equiv 1 \) (mod \( p \)) and \( (p-1)!\equiv -1 \) (mod \( p \)) there exists an even integer \( A \) such that \( A\equiv -1 \) (mod \( p \)) and \( (p-1)!=A(p-1)^2 \). This means that there exists an odd integer \( m \) satisfying \( A=mp-1 \). Hence \[ f(n)=\frac{(mp-1)(p-1)^2}{(p-1)^2\cdot p}=m-\frac1p.\] Therefore the closest integer to \( f(n) \) is \( m \), and that number is odd.
Problem 8 Does there exist \( k,n\in\mathbb N \) such that \( k\geq 2 \) and for which the set \( \{n,n+1,n+2, \dots, n+101\} \) can be partitioned into \( k \) disjoint subsets all of which have equal products of elements? The answer is no. Assume the contrary, that such \( n \) and \( k \) exist. Notice that \( 101 \) is a prime number. Therefore at most two of the numbers \( \{n, \dots, n+1\} \) are divisible by \( 101 \) which implies that \( k\leq 2 \). Thus \( k=2 \). Denote by \( A_1 \) and \( A_2 \) the two sets in a partition, and by \( \alpha \) the products of elements in each of them. Notice that \( 103 \) is a prime number and there is at most one element of \( \{n, n+1,\dots, n+101\} \) divisible by \( 103 \). Thus none of the elements is divisible by \( 103 \) and by Wilson’s theorem we have \( \alpha^2\equiv -1 \) (mod \( 103 \)) and we see that \( -1 \) is a quadratic residue modulo \( 103 \) which is impossible by Euler’s criterion (Theorem 5 from Quadratic congruences). |

2005-2018 IMOmath.com | imomath"at"gmail.com | Math rendered by MathJax Home | Olympiads | Book | Training | IMO Results | Forum | Links | About | Contact us |