Number Theory: Divisibility and Prime Numbers: Difficult Problems with Solutions

Solution:
Let [tex]d[/tex] be the greatest common divisor of the two numbers. Then [tex]d[/tex] divides every integer linear combination of them, in particular
[tex]\left(2^{2004}-1\right)-4\left(2^{2002}-1\right)=2^{2004}-1-2^{2004}+4=3[/tex]
Hence [tex]d=1[/tex] or [tex]d=3[/tex]. On the other hand, [tex]4\equiv 1\pmod 3[/tex], so both numbers are divisible by [tex]3[/tex]:
[tex]2^{2002}-1=4^{1001}-1\equiv 1-1=0\pmod 3,\qquad 2^{2004}-1=4^{1002}-1\equiv 1-1=0\pmod 3[/tex]
Therefore [tex]d=3[/tex]. (This agrees with the general rule [tex]\gcd\left(2^m-1, 2^n-1\right)=2^{\gcd(m, n)}-1[/tex]: here [tex]\gcd(2002, 2004)=2[/tex] and [tex]2^2-1=3[/tex].)

Solution:
The last two digits of a number are determined by its remainder modulo [tex]100[/tex], and the last two digits of a product depend only on the last two digits of the factors. Hence
[tex]666^{666}\equiv 66^{666}\pmod{100}[/tex]
We compute powers of [tex]66[/tex] modulo [tex]100[/tex]:
[tex]66^2=4356\equiv 56,\quad 66^4\equiv 56^2=3136\equiv 36,\quad 66^5\equiv 36\times 66=2376\equiv 76\pmod{100}[/tex]
Since [tex]76^2=5776\equiv 76\pmod{100}[/tex], every power [tex]76^k[/tex] with [tex]k\ge 1[/tex] ends in [tex]76[/tex]. As [tex]666=5\times 133+1[/tex], we get
[tex]66^{666}=\left(66^5\right)^{133}\times 66\equiv 76\times 66=5016\equiv 16\pmod{100}[/tex]
So the number [tex]666^{666}[/tex] ends in [tex]16[/tex].

Solution:
If [tex]N=q_1^{a_1}q_2^{a_2}\ldots q_k^{a_k}[/tex] is the prime factorization of [tex]N[/tex], then the number of divisors of [tex]N[/tex] is [tex](a_1+1)(a_2+1)\ldots(a_k+1)[/tex].
For [tex]p=2[/tex]: [tex]p^2+11=15=3\times 5[/tex] has [tex]4[/tex] divisors, so [tex]p=2[/tex] is rejected. For [tex]p=3[/tex]: [tex]p^2+11=20=2^2\times 5[/tex] has [tex](2+1)(1+1)=6[/tex] divisors, so [tex]p=3[/tex] fits.
Now let [tex]p\ge 5[/tex]. Then [tex]p[/tex] is odd, so [tex]p^2\equiv 1\pmod 4[/tex] and [tex]4\mid p^2+11[/tex]; also [tex]3\nmid p[/tex], so [tex]p^2\equiv 1\pmod 3[/tex] and [tex]3\mid p^2+11[/tex]. Hence
[tex]p^2+11=2^a\times 3^b\times m,\qquad a\ge 2,\ b\ge 1[/tex]
where [tex]m[/tex] is divisible neither by [tex]2[/tex] nor by [tex]3[/tex]. If [tex]d(m)[/tex] denotes the number of divisors of [tex]m[/tex], then the number of divisors of [tex]p^2+11[/tex] is
[tex](a+1)(b+1)\times d(m)\ge 3\times 2\times 1=6[/tex]
Equality holds only for [tex]a=2[/tex], [tex]b=1[/tex], [tex]m=1[/tex], i.e. [tex]p^2+11=12[/tex], which is impossible because [tex]p^2+11\ge 36[/tex]. So for [tex]p\ge 5[/tex] the number [tex]p^2+11[/tex] has more than [tex]6[/tex] divisors. The only such prime is [tex]p=3[/tex].

Solution:
Let [tex]N=2^3\times 3^4\times 5^6[/tex]. Both [tex]x[/tex] and [tex]y[/tex] divide their least common multiple [tex]N[/tex], so
[tex]x=2^{a_1}3^{b_1}5^{c_1},\qquad y=2^{a_2}3^{b_2}5^{c_2}[/tex]
with non-negative integer exponents. The least common multiple takes the larger exponent of each prime, so [tex]\operatorname{lcm}(x, y)=N[/tex] exactly when
[tex]\max(a_1, a_2)=3,\qquad \max(b_1, b_2)=4,\qquad \max(c_1, c_2)=6[/tex]
and the three conditions are independent. For the prime [tex]2[/tex]: there are [tex]4^2=16[/tex] pairs [tex](a_1, a_2)[/tex] with [tex]0\le a_1, a_2\le 3[/tex], and in [tex]3^2=9[/tex] of them both exponents are at most [tex]2[/tex]; hence in [tex]16-9=7[/tex] pairs the maximum is exactly [tex]3[/tex]. In the same way the prime [tex]3[/tex] gives [tex]5^2-4^2=9[/tex] pairs and the prime [tex]5[/tex] gives [tex]7^2-6^2=13[/tex] pairs.
By the multiplication principle the number of ordered pairs is
[tex]7\times 9\times 13=819[/tex]

Solution:
Since [tex]323=17\times 19[/tex], where [tex]17[/tex] and [tex]19[/tex] are distinct primes, it is enough to prove that [tex]a_n[/tex] is divisible by [tex]17[/tex] and by [tex]19[/tex]. We use two facts. First, [tex]x-y[/tex] divides [tex]x^k-y^k[/tex] for every natural [tex]k[/tex], because
[tex]x^k-y^k=(x-y)\left(x^{k-1}+x^{k-2}y+\ldots+y^{k-1}\right)[/tex]
Second, [tex]x^{2n}-y^{2n}=\left(x^2\right)^n-\left(y^2\right)^n[/tex] is divisible by [tex]x^2-y^2=(x-y)(x+y)[/tex], hence also by [tex]x+y[/tex].
Divisibility by [tex]17[/tex]: we write
[tex]a_n=\left(20^{2n}-3^{2n}\right)+\left(16^{2n}-1^{2n}\right)[/tex]
The first bracket is divisible by [tex]20-3=17[/tex] (first fact) and the second by [tex]16+1=17[/tex] (second fact).
Divisibility by [tex]19[/tex]: we write
[tex]a_n=\left(20^{2n}-1^{2n}\right)+\left(16^{2n}-3^{2n}\right)[/tex]
The first bracket is divisible by [tex]20-1=19[/tex] (first fact) and the second by [tex]16+3=19[/tex] (second fact).
Since [tex]17[/tex] and [tex]19[/tex] are coprime, [tex]a_n[/tex] is divisible by [tex]17\times 19=323[/tex].

Solution:
Assume that [tex]121\mid n^2+3n+5[/tex] for some natural [tex]n[/tex]. Then [tex]121[/tex] also divides
[tex]4\left(n^2+3n+5\right)=4n^2+12n+20=(2n+3)^2+11[/tex]
In particular [tex]11\mid (2n+3)^2+11[/tex], so [tex]11\mid (2n+3)^2[/tex]. Since [tex]11[/tex] is a prime, [tex]11\mid 2n+3[/tex], and therefore [tex]121\mid (2n+3)^2[/tex].
Now [tex]121\mid (2n+3)^2+11[/tex] and [tex]121\mid (2n+3)^2[/tex] give [tex]121\mid 11[/tex], which is false. This contradiction shows that [tex]n^2+3n+5[/tex] is never divisible by [tex]121[/tex].
(The number can be divisible by [tex]11[/tex]: for example, for [tex]n=4[/tex] it equals [tex]33[/tex]. So the argument really needs the square [tex]121=11^2[/tex].)

Solution:
Let [tex]A=20x+17y[/tex], [tex]B=17x+20y[/tex] and let [tex]d[/tex] be their greatest common divisor. Then [tex]d[/tex] divides
[tex]20A-17B=(400-289)x=111x,\qquad 20B-17A=(400-289)y=111y[/tex]
Hence [tex]d[/tex] divides [tex]\gcd(111x, 111y)=111\times \gcd(x, y)=111[/tex], so [tex]d\le 111[/tex].
The value [tex]111=3\times 37[/tex] is attained. For example, for the coprime numbers [tex]x=1[/tex], [tex]y=38[/tex] (chosen so that [tex]x\equiv y\pmod{37}[/tex] and [tex]3\mid x+y[/tex]) we get
[tex]A=20+646=666=6\times 111,\qquad B=17+760=777=7\times 111[/tex]
and since [tex]6[/tex] and [tex]7[/tex] are coprime, the greatest common divisor of [tex]A[/tex] and [tex]B[/tex] equals [tex]111[/tex]. The greatest possible value is [tex]111[/tex].

Solution:
If [tex]n=p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}[/tex] is the prime factorization of [tex]n[/tex], then the number of its divisors is [tex](a_1+1)(a_2+1)\ldots(a_k+1)[/tex]. Since [tex]9[/tex] can be written as a product of factors greater than [tex]1[/tex] only as [tex]9[/tex] or [tex]3\times 3[/tex], the number [tex]n[/tex] has exactly [tex]9[/tex] divisors if and only if [tex]n=p^8[/tex] or [tex]n=p^2q^2[/tex] with distinct primes [tex]p[/tex] and [tex]q[/tex].
Case [tex]n=p^8[/tex]: [tex]2^8=256\lt 5000[/tex], [tex]3^8=6561[/tex] lies in the range and [tex]5^8=390625\gt 8000[/tex], so this case gives [tex]1[/tex] number.
Case [tex]n=(pq)^2[/tex]: since [tex]70^2=4900\lt 5000\le 71^2=5041[/tex] and [tex]89^2=7921\le 8000\lt 90^2=8100[/tex], we need
[tex]71\le pq\le 89[/tex]
In this interval the products of two distinct primes are
[tex]74=2\times 37,\quad 77=7\times 11,\quad 82=2\times 41,\quad 85=5\times 17,\quad 86=2\times 43,\quad 87=3\times 29[/tex]
The other numbers are primes ([tex]71, 73, 79, 83, 89[/tex]) or are divisible by the square of a prime or have three prime factors ([tex]72, 75, 76, 78, 80, 81, 84, 88[/tex]). So this case gives [tex]6[/tex] numbers:
[tex]74^2=5476, \ 77^2=5929, \ 82^2=6724, \ 85^2=7225, \ 86^2=7396, \ 87^2=7569[/tex]
In total there are [tex]1+6=7[/tex] such numbers.

Solution:
Denote the number by [tex]f(n)[/tex] and factor it:
[tex]f(n)=n\left(9n^4-5n^2-4\right)=n\left(n^2-1\right)\left(9n^2+4\right)=(n-1)n(n+1)\left(9n^2+4\right)[/tex]
Let [tex]D[/tex] be the required greatest common divisor. Then [tex]D[/tex] divides the numbers
[tex]f(2)=1\times 2\times 3\times 40=240=2^4\times 3\times 5,\qquad f(3)=2\times 3\times 4\times 85=2040=2^3\times 3\times 5\times 17[/tex]
so [tex]D[/tex] divides their greatest common divisor [tex]2^3\times 3\times 5=120[/tex]. We show that [tex]120=3\times 8\times 5[/tex] divides [tex]f(n)[/tex] for every [tex]n[/tex].
Divisibility by [tex]3[/tex]: one of the three consecutive numbers [tex]n-1[/tex], [tex]n[/tex], [tex]n+1[/tex] is divisible by [tex]3[/tex].
Divisibility by [tex]8[/tex]: if [tex]n[/tex] is odd, then [tex]n-1[/tex] and [tex]n+1[/tex] are consecutive even numbers and one of them is divisible by [tex]4[/tex], so [tex]8\mid (n-1)(n+1)[/tex]. If [tex]n=2k[/tex] is even, then [tex]9n^2+4=4\left(9k^2+1\right)[/tex] is divisible by [tex]4[/tex] and [tex]n[/tex] is divisible by [tex]2[/tex], so [tex]8\mid n\left(9n^2+4\right)[/tex].
Divisibility by [tex]5[/tex]: if [tex]n[/tex] gives remainder [tex]0[/tex], [tex]1[/tex] or [tex]4[/tex] when divided by [tex]5[/tex], then one of [tex]n[/tex], [tex]n-1[/tex], [tex]n+1[/tex] is divisible by [tex]5[/tex]. If the remainder is [tex]2[/tex] or [tex]3[/tex], then [tex]n^2\equiv 4\pmod{5}[/tex] and
[tex]9n^2+4\equiv 9\times 4+4=40\equiv 0\pmod{5}[/tex]
Since [tex]3[/tex], [tex]8[/tex] and [tex]5[/tex] are pairwise coprime, [tex]120\mid f(n)[/tex] for every natural [tex]n[/tex]. Therefore [tex]D=120[/tex].

Solution:
Factor [tex]P[/tex] using the difference of squares:
[tex]P=a\left[\left(a\left(a^2-7\right)\right)^2-6^2\right]=a\left(a^3-7a-6\right)\left(a^3-7a+6\right)[/tex]
The polynomial [tex]a^3-7a-6[/tex] has the root [tex]a=-1[/tex], and [tex]a^3-7a+6[/tex] has the root [tex]a=1[/tex]; dividing by the corresponding linear factors, we get
[tex]a^3-7a-6=(a+1)(a+2)(a-3),\qquad a^3-7a+6=(a-1)(a-2)(a+3)[/tex]
Hence [tex]P[/tex] is the product of seven consecutive integers:
[tex]P=(a-3)(a-2)(a-1)\,a\,(a+1)(a+2)(a+3)[/tex]
We have [tex]5040=2^4\times 3^2\times 5\times 7[/tex]. Among any seven consecutive integers there is a multiple of [tex]7[/tex] and a multiple of [tex]5[/tex]; there are at least two multiples of [tex]3[/tex], so the product is divisible by [tex]3^2[/tex]; there are at least three consecutive even numbers, and of any two consecutive even numbers one is divisible by [tex]4[/tex], so these three numbers give a factor of at least [tex]2\times 2\times 4=2^4[/tex].
Since [tex]16[/tex], [tex]9[/tex], [tex]5[/tex] and [tex]7[/tex] are pairwise coprime and each of them divides [tex]P[/tex], their product divides [tex]P[/tex]:
[tex]16\times 9\times 5\times 7=5040\mid P[/tex]

Solution:
Let [tex]x=5^{\frac{p-1}{2}}[/tex]; it is an integer because [tex]p[/tex] is odd.
Case [tex]p=5[/tex]: [tex]x+10=5^2+10=35[/tex] is divisible by [tex]5[/tex], so [tex]p=5[/tex] works.
Case [tex]p\ne 5[/tex]: by Fermat's little theorem [tex]p[/tex] divides
[tex]5^{p-1}-1=x^2-1=(x-1)(x+1)[/tex]
and since [tex]p[/tex] is prime, [tex]p\mid x-1[/tex] or [tex]p\mid x+1[/tex].
If [tex]p\mid x-1[/tex], then [tex]p\mid (x+10)-(x-1)=11[/tex], so [tex]p=11[/tex]. If [tex]p\mid x+1[/tex], then [tex]p\mid (x+10)-(x+1)=9[/tex], so [tex]p=3[/tex].
Check: for [tex]p=3[/tex] we get [tex]5+10=15[/tex], which is divisible by [tex]3[/tex]; for [tex]p=11[/tex] we get [tex]5^5+10=3135=11\times 285[/tex].
Hence [tex]p\in\{3, \,5, \,11\}[/tex]. The case [tex]p=5[/tex] is easy to miss, because Fermat's theorem does not apply to it.

Solution:
The condition means that [tex]x^2[/tex] and [tex]x[/tex] have the same last three digits, i.e.
[tex]x^2\equiv x\pmod{1000}\iff 1000\mid x(x-1),\qquad 100\le x\le 999[/tex]
Since [tex]1000=8\times 125[/tex] and the consecutive numbers [tex]x-1[/tex] and [tex]x[/tex] are coprime, the factor [tex]8=2^3[/tex] divides one of them entirely, and so does [tex]125=5^3[/tex]. If both divide the same number, then [tex]1000\mid x[/tex] or [tex]1000\mid x-1[/tex], which is impossible for a three-digit [tex]x[/tex]. Two cases remain.
Case [tex]1[/tex]: [tex]125\mid x[/tex] and [tex]8\mid x-1[/tex]. The three-digit multiples of [tex]125[/tex] are [tex]125, 250, 375, 500, 625, 750, 875[/tex], and their remainders when divided by [tex]8[/tex] are [tex]5, 2, 7, 4, 1, 6, 3[/tex]. Only [tex]x=625[/tex] gives remainder [tex]1[/tex].
Case [tex]2[/tex]: [tex]8\mid x[/tex] and [tex]125\mid x-1[/tex]. Then [tex]x\in\{126, 251, 376, 501, 626, 751, 876\}[/tex]. The odd numbers are not divisible by [tex]8[/tex], and among [tex]126, 376, 626, 876[/tex] only [tex]376=8\times 47[/tex] is divisible by [tex]8[/tex].
Check:
[tex]625^2=390625,\qquad 376^2=141376[/tex]
The required numbers are [tex]376[/tex] and [tex]625[/tex].

Solution:
Each of the primes [tex]17[/tex], [tex]19[/tex], [tex]23[/tex] divides exactly one of the numbers [tex]1, 2, \ldots, 26[/tex], because [tex]2\times 17=34\gt 26[/tex]. If, for example, [tex]17[/tex] is not crossed out, then the product of its group is divisible by [tex]17[/tex] and the product of the other group is not, so the products are not equal. Hence [tex]17[/tex], [tex]19[/tex] and [tex]23[/tex] must be crossed out.
If the remaining numbers are split into two groups with equal products [tex]Q[/tex], then the product of all remaining numbers is [tex]Q^2[/tex], a perfect square. The exponent of [tex]2[/tex] in [tex]26![/tex] is
[tex]\left\lfloor\frac{26}{2}\right\rfloor+\left\lfloor\frac{26}{4}\right\rfloor+\left\lfloor\frac{26}{8}\right\rfloor+\left\lfloor\frac{26}{16}\right\rfloor=13+6+3+1=23[/tex]
Crossing out the odd numbers [tex]17[/tex], [tex]19[/tex], [tex]23[/tex] does not change it, so the product of the other [tex]23[/tex] numbers contains [tex]2[/tex] to an odd power and is not a perfect square. Thus at least one more number must be crossed out, i.e. at least [tex]4[/tex] numbers in total.
Four numbers are enough: cross out [tex]14[/tex], [tex]17[/tex], [tex]19[/tex], [tex]23[/tex]. The remaining numbers can be split into the groups [tex]\{1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 24, 25, 26\}[/tex] and [tex]\{10, 12, 13, 15, 16, 18, 20, 21, 22\}[/tex], and the product of each group equals
[tex]2^{11}\times 3^5\times 5^3\times 7\times 11\times 13[/tex]
Therefore the least number is [tex]4[/tex].

Solution:
Let the numbers in the chosen order be [tex]a_1, a_2, \ldots, a_{11}[/tex]. Each of them has four digits, so the resulting number is
[tex]N=a_1\times 10^{40}+a_2\times 10^{36}+\ldots+a_{10}\times 10^{4}+a_{11}[/tex]
Since [tex]10^4-1=9999=11\times 909[/tex] and [tex]10^{4j}-1=\left(10^4\right)^j-1[/tex] is divisible by [tex]10^4-1[/tex], every number [tex]10^{4j}-1[/tex] is divisible by [tex]11[/tex]. Therefore the difference
[tex]N-\left(a_1+a_2+\ldots+a_{11}\right)=a_1\left(10^{40}-1\right)+a_2\left(10^{36}-1\right)+\ldots+a_{10}\left(10^{4}-1\right)[/tex]
is divisible by [tex]11[/tex]. The sum [tex]a_1+a_2+\ldots+a_{11}[/tex] does not depend on the order; it is the sum of eleven consecutive numbers with middle term [tex]2014[/tex]:
[tex]2009+2010+\ldots+2019=11\times 2014[/tex]
Hence [tex]11\mid N[/tex] for every order of the numbers. Since [tex]N\gt 11[/tex], the number [tex]N[/tex] has a divisor different from [tex]1[/tex] and from [tex]N[/tex], so it is not prime.

Solution:
If a prison has [tex]n[/tex] floors, it has [tex]n\times n\times n=n^3[/tex] prisoners and each of them receives [tex]n[/tex] dollars, so this prison costs [tex]n^3\times n=n^4[/tex] dollars. Hence the total cost is
[tex]S=n_1^4+n_2^4+\ldots+n_{14}^4[/tex]
where [tex]n_1, n_2, \ldots, n_{14}[/tex] are natural numbers. Consider remainders when dividing by [tex]16[/tex]. If [tex]n=2k[/tex] is even, then [tex]n^4=16k^4\equiv 0\pmod{16}[/tex]. If [tex]n=2k+1[/tex] is odd, then [tex]n^2=4k(k+1)+1=8t+1[/tex] for some integer [tex]t[/tex], because [tex]k(k+1)[/tex] is even, and
[tex]n^4=(8t+1)^2=64t^2+16t+1\equiv 1\pmod{16}[/tex]
Therefore [tex]S\equiv r\pmod{16}[/tex], where [tex]r[/tex] is the number of prisons with an odd number of floors and [tex]0\le r\le 14[/tex]. So the remainder of [tex]S[/tex] when divided by [tex]16[/tex] is one of the numbers [tex]0, 1, \ldots, 14[/tex]. On the other hand,
[tex]1\,599\,999=16\times 100\,000-1=16\times 99\,999+15[/tex]
gives remainder [tex]15[/tex] when divided by [tex]16[/tex]. Hence the total cost cannot be [tex]1\,599\,999[/tex] dollars, and the official made a mistake.