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

Solution:
Note that [tex]11111=41\times 271[/tex]. Hence for every digit [tex]d[/tex] the five-digit number
[tex]\overline{ddddd}=d\times 11111=41d\times 271[/tex]
is a multiple of [tex]271[/tex].
The written number has [tex]37[/tex] digits, each of them one of the nine digits from [tex]1[/tex] to [tex]9[/tex]. If every digit occurred at most [tex]4[/tex] times, the number would have at most [tex]9\times 4=36\lt 37[/tex] digits. Therefore some digit [tex]d[/tex] occurs at least [tex]5[/tex] times (pigeonhole principle).
Zapryan keeps five of the digits [tex]d[/tex] and erases all the other [tex]32[/tex] digits. The remaining number is [tex]\overline{ddddd}[/tex], which is divisible by [tex]271[/tex]. So whatever number Strahil writes, Zapryan can always obtain a multiple of [tex]271[/tex].

Solution:
Bounds. The number [tex]A[/tex] has [tex]26[/tex] digits, so
[tex]10^{25}\le p^{13}\lt 10^{26}=100^{13}\Rightarrow p\lt 100[/tex]
Also [tex]80^{13}=8^{13}\times 10^{13}=2^{39}\times 10^{13}[/tex], where
[tex]2^{39}=\frac{1024^4}{2}\lt \frac{1100^4}{2}=\frac{14641\times 10^{8}}{2}\lt 10^{12}[/tex]
Hence [tex]80^{13}\lt 10^{25}\le p^{13}[/tex], so [tex]p\gt 80[/tex].
Last digit. The last digit of [tex]p^{13}[/tex] depends only on the last digit of [tex]p[/tex], and the last digits of the powers of any digit repeat with period [tex]1[/tex], [tex]2[/tex] or [tex]4[/tex] (for example, the powers of [tex]7[/tex] end in [tex]7[/tex], [tex]9[/tex], [tex]3[/tex], [tex]1[/tex], and then this repeats). Since [tex]13=1+3\times 4[/tex], the numbers [tex]p^{13}[/tex] and [tex]p[/tex] end in the same digit. The number [tex]A[/tex] ends in [tex]9[/tex], so [tex]p[/tex] ends in [tex]9[/tex], and together with [tex]80\lt p\lt 100[/tex] this leaves [tex]p=89[/tex] or [tex]p=99[/tex].
Divisibility by [tex]3[/tex]. The digit sum of [tex]A[/tex] is [tex]107[/tex], which is not divisible by [tex]3[/tex], so [tex]A[/tex] is not divisible by [tex]3[/tex]. If [tex]p=99[/tex], then [tex]A=99^{13}[/tex] would be divisible by [tex]3[/tex], a contradiction. Hence [tex]p=89[/tex].

Solution:
Let [tex]D=53^m-37^n[/tex]. The numbers [tex]53^m[/tex] and [tex]37^n[/tex] are powers of different primes, so they are not equal and [tex]D\ne 0[/tex].
Modulo [tex]4[/tex] we have [tex]53\equiv 37\equiv 1[/tex], hence
[tex]D\equiv 1-1=0\pmod 4[/tex]
Modulo [tex]9[/tex] we have [tex]53\equiv -1[/tex] and [tex]37\equiv 1[/tex], hence
[tex]D\equiv (-1)^m-1\pmod 9[/tex]
that is, [tex]D\equiv 0\pmod 9[/tex] when [tex]m[/tex] is even and [tex]D\equiv -2\equiv 7\pmod 9[/tex] when [tex]m[/tex] is odd. So [tex]D[/tex] is a non-zero multiple of [tex]4[/tex] that leaves remainder [tex]0[/tex] or [tex]7[/tex] when divided by [tex]9[/tex].
The non-zero multiples of [tex]4[/tex] with absolute value less than [tex]16[/tex] are [tex]\pm 4[/tex], [tex]\pm 8[/tex], [tex]\pm 12[/tex], and modulo [tex]9[/tex]
[tex]4\equiv 4,\quad -4\equiv 5,\quad 8\equiv 8,\quad -8\equiv 1,\quad 12\equiv 3,\quad -12\equiv 6[/tex]
None of these remainders is [tex]0[/tex] or [tex]7[/tex], hence [tex]|D|\ge 16[/tex]. For [tex]m=n=1[/tex] we get [tex]|53-37|=16[/tex], so the smallest value is [tex]16[/tex].

Solution:
The exponents of [tex]5[/tex] and of [tex]2[/tex] in the prime factorization of [tex]34![/tex] are
[tex]\left\lfloor\frac{34}{5}\right\rfloor+\left\lfloor\frac{34}{25}\right\rfloor=6+1=7[/tex]
[tex]\left\lfloor\frac{34}{2}\right\rfloor+\left\lfloor\frac{34}{4}\right\rfloor+\left\lfloor\frac{34}{8}\right\rfloor+\left\lfloor\frac{34}{16}\right\rfloor+\left\lfloor\frac{34}{32}\right\rfloor=17+8+4+2+1=32[/tex]
Hence [tex]34!=10^7\times M[/tex], where [tex]M[/tex] is not divisible by [tex]5[/tex] (so its last digit is not [tex]0[/tex]) and [tex]M[/tex] is divisible by [tex]2^{25}[/tex]. Thus [tex]34![/tex] ends in exactly seven zeros. In the given record [tex]b[/tex] is followed by six zeros, therefore [tex]b=0[/tex] and [tex]a[/tex] is the last digit of [tex]M[/tex].
Since [tex]8\mid M[/tex], the number formed by the last three digits of [tex]M[/tex] is divisible by [tex]8[/tex]:
[tex]8\mid\overline{35a}=350+a=8\times 43+6+a\ \Rightarrow\ 8\mid 6+a\ \Rightarrow\ a=2[/tex]
Next, [tex]9\mid 34![/tex], so the sum of its digits is divisible by [tex]9[/tex]. The known digits (with [tex]a=2[/tex], [tex]b=0[/tex]) add up to [tex]141=9\times 15+6[/tex], hence
[tex]c+d\equiv 3\pmod 9,\quad 0\le c+d\le 18\ \Rightarrow\ c+d=3\text{ or }c+d=12[/tex]
Also [tex]11\mid 34![/tex], so the difference between the sum of the digits in odd places and the sum of the digits in even places (counting from the right, the units digit being in place [tex]1[/tex]) is divisible by [tex]11[/tex]. The known digits give [tex]80[/tex] in odd places and [tex]61[/tex] in even places, while [tex]d[/tex] is in place [tex]29[/tex] (odd) and [tex]c[/tex] in place [tex]30[/tex] (even). Hence
[tex]11\mid (80+d)-(61+c)=19+d-c\ \Rightarrow\ d-c\equiv 3\pmod{11}[/tex]
[tex]-9\le d-c\le 9\ \Rightarrow\ d-c=3\text{ or }d-c=-8[/tex]
The numbers [tex]c+d[/tex] and [tex]d-c[/tex] have the same parity (their sum is [tex]2d[/tex]), so only two cases are possible:
[tex]\begin{cases}c+d=3\\ d-c=3\end{cases}\Rightarrow\ c=0,\ d=3[/tex]
[tex]\begin{cases}c+d=12\\ d-c=-8\end{cases}\Rightarrow\ c=10,\ d=2[/tex]
In the second case [tex]c=10[/tex] is not a digit. Therefore [tex]a=2[/tex], [tex]b=0[/tex], [tex]c=0[/tex], [tex]d=3[/tex].

Solution:
Denote by [tex]S(m)[/tex] the sum of the digits of [tex]m[/tex], and let [tex]n[/tex] end in exactly [tex]k\ge 0[/tex] nines. Adding [tex]1[/tex] turns these nines into zeros and increases the preceding digit (which is not [tex]9[/tex], possibly a leading zero) by [tex]1[/tex], so
[tex]S(n+1)=S(n)+1-9k[/tex]
If both digit sums are divisible by [tex]7[/tex], then
[tex]7\mid 9k-1=7k+(2k-1)\ \Rightarrow\ 7\mid 2k-1\ \Rightarrow\ k\in\{4, \,11, \,18, \,\ldots\}[/tex]
In particular, [tex]n[/tex] ends in at least four nines. For [tex]k=4[/tex] we have [tex]n=10000m+9999[/tex], where [tex]m\ge 0[/tex] does not end in [tex]9[/tex], and
[tex]S(n)=S(m)+36,\qquad 7\mid S(m)+36\ \Leftrightarrow\ S(m)\equiv 6\pmod 7[/tex]
For [tex]0\le m\le 5[/tex] we have [tex]S(m)=m\lt 6[/tex], so the smallest suitable value is [tex]m=6[/tex], which gives [tex]n=69999[/tex]. Every [tex]n[/tex] with [tex]k\ge 11[/tex] has at least [tex]11[/tex] digits and is larger. Check:
[tex]S(69999)=42=7\times 6,\qquad S(70000)=7[/tex]
Hence the smallest such number is [tex]n=69999[/tex].

Solution:
Let [tex]8n+1=a^2[/tex] and [tex]24n+1=b^2[/tex], where [tex]a[/tex] and [tex]b[/tex] are positive integers. Then
[tex]3a^2-b^2=3(8n+1)-(24n+1)=2[/tex]
Hence
[tex]8n+3=a^2+2=a^2+\left(3a^2-b^2\right)=4a^2-b^2=(2a-b)(2a+b)[/tex]
Since [tex]8n+3\gt 0[/tex] and [tex]2a+b\gt 0[/tex], we have [tex]2a-b\ge 1[/tex]. Suppose that [tex]2a-b=1[/tex], i.e. [tex]b=2a-1[/tex]. Substituting into [tex]3a^2-b^2=2[/tex]:
[tex]3a^2-(2a-1)^2=2\ \Rightarrow\ a^2-4a+3=0\ \Rightarrow\ a=1\text{ or }a=3[/tex]
Then [tex]8n+1=1[/tex] or [tex]8n+1=9[/tex], i.e. [tex]n=0[/tex] or [tex]n=1[/tex], which contradicts [tex]n\gt 1[/tex]. Therefore [tex]2a-b\ge 2[/tex], and also [tex]2a+b\gt 2a-b\ge 2[/tex].
So [tex]8n+3[/tex] is the product of two integers greater than [tex]1[/tex], i.e. it is composite. (The condition [tex]n\gt 1[/tex] is essential: for [tex]n=1[/tex] the number [tex]8n+3=11[/tex] is prime.)

Solution:
Using [tex]\left(2^{2^k}-1\right)\left(2^{2^k}+1\right)=2^{2^{k+1}}-1[/tex] repeatedly, starting from [tex]2^{2^0}-1=1[/tex], we get
[tex]F_0F_1\ldots F_{n-1}=\left(2^{2^0}-1\right)F_0F_1\ldots F_{n-1}=2^{2^n}-1=F_n-2[/tex]
Hence the Fermat numbers are pairwise coprime: if [tex]m\lt n[/tex] and [tex]d[/tex] divides both [tex]F_m[/tex] and [tex]F_n[/tex], then [tex]d[/tex] divides [tex]F_0F_1\ldots F_{n-1}=F_n-2[/tex] (one of the factors is [tex]F_m[/tex]) and [tex]F_n[/tex], so [tex]d\mid 2[/tex]; all [tex]F_n[/tex] are odd, therefore [tex]d=1[/tex].
Consequently the least common multiple of [tex]F_2, F_3, \ldots, F_{1985}[/tex] equals their product, which has [tex]1985-1=1984[/tex] factors. For [tex]n\ge 2[/tex]
[tex]2^{2^n}=\left(2^4\right)^{2^{n-2}}=16^{2^{n-2}}[/tex]
and every power of a number ending in [tex]6[/tex] ends in [tex]6[/tex] (since [tex]6\times 6=36[/tex]). So [tex]2^{2^n}[/tex] ends in [tex]6[/tex] and [tex]F_n[/tex] ends in [tex]7[/tex]; hence the product ends in the same digit as [tex]7^{1984}[/tex].
The last digits of [tex]7^1, 7^2, 7^3, 7^4, \ldots[/tex] are [tex]7, \ 9, \ 3, \ 1[/tex] and repeat with period [tex]4[/tex]. Since [tex]1984=4\times 496[/tex], the number [tex]7^{1984}[/tex] ends in [tex]1[/tex]. So the units digit of the least common multiple is [tex]1[/tex].

Solution:
Denote the number by [tex]R[/tex]; then [tex]9R=10^{2^n}-1[/tex]. Applying [tex]x^2-1=(x-1)(x+1)[/tex] repeatedly, we get
[tex]10^{2^n}-1=\left(10^{2^{n-1}}-1\right)\left(10^{2^{n-1}}+1\right)=\ldots[/tex]
[tex]\ldots=(10-1)(10+1)\left(10^2+1\right)\left(10^4+1\right)\ldots\left(10^{2^{n-1}}+1\right)[/tex]
Hence [tex]R=A_0A_1\ldots A_{n-1}[/tex], where [tex]A_k=10^{2^k}+1[/tex]. These [tex]n[/tex] factors are pairwise coprime. Indeed, let [tex]i\lt j[/tex]. By the same factorization (with [tex]j[/tex] in place of [tex]n[/tex]), the number [tex]10^{2^j}-1=9A_0A_1\ldots A_{j-1}[/tex] is divisible by [tex]A_i[/tex], therefore
[tex]A_j=\left(10^{2^j}-1\right)+2\equiv 2\pmod{A_i}[/tex]
so every common divisor of [tex]A_i[/tex] and [tex]A_j[/tex] divides [tex]2[/tex]; since [tex]A_i[/tex] is odd, [tex]A_i[/tex] and [tex]A_j[/tex] are coprime.
Each [tex]A_k\gt 1[/tex] has a prime divisor [tex]p_k[/tex]. Since the [tex]A_k[/tex] are pairwise coprime, the primes [tex]p_0, p_1, \ldots, p_{n-1}[/tex] are pairwise distinct, and all of them divide [tex]R[/tex].
For every subset of [tex]\left\{p_0, p_1, \ldots, p_{n-1}\right\}[/tex] the product of its elements (the empty product being [tex]1[/tex]) is a divisor of [tex]R[/tex], and by the uniqueness of prime factorization different subsets give different products. There are [tex]2^n[/tex] subsets, so [tex]R[/tex] has at least [tex]2^n[/tex] distinct divisors.

Solution:
For [tex]N=1[/tex] take [tex]M=1[/tex] (it is not divisible by [tex]2[/tex], [tex]3[/tex], [tex]4[/tex]); for [tex]N=2[/tex] take [tex]M=2[/tex] (it is not divisible by [tex]3[/tex], [tex]4[/tex], [tex]5[/tex]). So [tex]N=1[/tex] and [tex]N=2[/tex] are possible.
Now let [tex]N\ge 3[/tex] and let [tex]k[/tex] be one of the numbers [tex]N+1[/tex], [tex]N+2[/tex], [tex]N+3[/tex]. If [tex]k[/tex] is not a power of a prime, then [tex]k=uv[/tex] with coprime [tex]u, v\gt 1[/tex] (take as [tex]u[/tex] the full power of one prime divisor of [tex]k[/tex]). Then
[tex]u, v\le\frac{k}{2}\le\frac{N+3}{2}\le N[/tex]
so [tex]u\mid M[/tex] and [tex]v\mid M[/tex], and since [tex]u[/tex] and [tex]v[/tex] are coprime, [tex]k=uv\mid M[/tex], a contradiction. Hence each of [tex]N+1[/tex], [tex]N+2[/tex], [tex]N+3[/tex] is a power of a prime.
One of these three consecutive numbers is divisible by [tex]3[/tex], so it equals [tex]3^b[/tex] with [tex]b\ge 1[/tex]; at least one of them is even, so it is a power of [tex]2[/tex]. If [tex]N+1[/tex] and [tex]N+3[/tex] were both even, they would be powers of [tex]2[/tex] differing by [tex]2[/tex], i.e. [tex]2[/tex] and [tex]4[/tex], which gives [tex]N=1\lt 3[/tex]. Therefore [tex]N+2=2^a[/tex], where [tex]a\ge 3[/tex] because [tex]N+2\ge 5[/tex], and the power of [tex]3[/tex] is [tex]N+1[/tex] or [tex]N+3[/tex]:
[tex]3^b=2^a-1\text{ or }3^b=2^a+1[/tex]
If [tex]3^b=2^a-1[/tex], then [tex]2^a\equiv 1\pmod 3[/tex]; as [tex]2\equiv -1\pmod 3[/tex], the exponent [tex]a=2c[/tex] is even, [tex]c\ge 2[/tex], and
[tex]\left(2^c-1\right)\left(2^c+1\right)=3^b[/tex]
Both factors are powers of [tex]3[/tex] differing by [tex]2[/tex], so they are [tex]1[/tex] and [tex]3[/tex], which gives [tex]c=1[/tex], a contradiction.
If [tex]3^b=2^a+1[/tex], then [tex]3^b\equiv 1\pmod 4[/tex] (as [tex]a\ge 3[/tex]); since [tex]3\equiv -1\pmod 4[/tex], the exponent [tex]b=2d[/tex] is even and
[tex]\left(3^d-1\right)\left(3^d+1\right)=2^a[/tex]
Both factors are powers of [tex]2[/tex] differing by [tex]2[/tex], so they are [tex]2[/tex] and [tex]4[/tex]. Hence [tex]d=1[/tex], [tex]b=2[/tex], [tex]a=3[/tex] and [tex]N=2^3-2=6[/tex]. Check: [tex]M=60[/tex] is divisible by [tex]1, \ 2, \ \ldots, \ 6[/tex] but not by [tex]7[/tex], [tex]8[/tex], [tex]9[/tex]. Therefore
[tex]N\in\{1, \,2, \,6\}[/tex]

Solution:
Let the primes be [tex]a_k=a+kd[/tex], [tex]0\le k\le 14[/tex], where [tex]d\gt 0[/tex].
Key observation: if a prime [tex]p[/tex] does not divide [tex]d[/tex], then any [tex]p[/tex] consecutive terms [tex]a_i, a_{i+1}, \ldots, a_{i+p-1}[/tex] give pairwise different remainders modulo [tex]p[/tex], because
[tex]a_j-a_k=(j-k)d,\quad 0\lt |j-k|\lt p\ \Rightarrow\ p\nmid (j-k)d[/tex]
So these [tex]p[/tex] terms take all [tex]p[/tex] remainders; one of them is divisible by [tex]p[/tex], and since it is prime, it equals [tex]p[/tex].
Step [tex]1[/tex]: [tex]p\in\{2, \,3, \,5, \,7\}[/tex]. If [tex]p\nmid d[/tex], apply the observation to the blocks [tex]a_0, \ldots, a_{p-1}[/tex] and [tex]a_p, \ldots, a_{2p-1}[/tex] (they exist, since [tex]2p-1\le 13[/tex]). Each block contains a term equal to [tex]p[/tex], so two terms with different indices are equal, which is impossible in a strictly increasing progression. Hence [tex]2[/tex], [tex]3[/tex], [tex]5[/tex] and [tex]7[/tex] divide [tex]d[/tex], so [tex]210\mid d[/tex] and [tex]d\ge 210[/tex].
Step [tex]2[/tex]: [tex]p\in\{11, \,13\}[/tex]. If [tex]p\nmid d[/tex], some term among [tex]a_0, \ldots, a_{p-1}[/tex] equals [tex]p[/tex]. For [tex]k\ge 1[/tex] we have [tex]a_k\ge 2+210\gt 13[/tex], so this term is [tex]a_0=p[/tex]. But then the term
[tex]a_p=p+pd=p(1+d)[/tex]
(it exists, since [tex]p\le 13\lt 14[/tex]) is divisible by [tex]p[/tex] and greater than [tex]p[/tex], hence it is not prime, a contradiction. So [tex]11\mid d[/tex] and [tex]13\mid d[/tex]. Therefore [tex]d[/tex] is divisible by
[tex]2\times 3\times 5\times 7\times 11\times 13=30030[/tex]
and hence [tex]d\ge 30030\gt 30000[/tex].

Solution:
We use Fermat's little theorem: [tex]5^r\equiv 5\pmod r[/tex] for every prime [tex]r[/tex]. The condition is symmetric in [tex]p[/tex] and [tex]q[/tex].
Case [tex]1[/tex]: [tex]p=5[/tex]. If [tex]q=5[/tex], then [tex]25\mid 2\times 5^5[/tex], so [tex](5, 5)[/tex] is a solution. If [tex]q\ne 5[/tex], divisibility by [tex]5[/tex] is automatic and [tex]5[/tex] and [tex]q[/tex] are coprime, so we need [tex]q\mid 5^5+5^q[/tex]. As [tex]5^q\equiv 5\pmod q[/tex], this means
[tex]q\mid 5^5+5=3130=2\times 5\times 313[/tex]
so [tex]q=2[/tex] or [tex]q=313[/tex] (the number [tex]313[/tex] is prime). Both work: [tex]5^5+5^2=3150=10\times 315[/tex], and [tex]5^5+5^{313}[/tex] is divisible by [tex]5[/tex] and, since [tex]5^5+5^{313}\equiv 3130\equiv 0\pmod{313}[/tex], also by [tex]313[/tex]. This gives [tex](5, 2)[/tex], [tex](5, 313)[/tex] and, by symmetry, [tex](2, 5)[/tex], [tex](313, 5)[/tex].
Case [tex]2[/tex]: [tex]p=2[/tex], [tex]q\ne 5[/tex]. The sum [tex]5^2+5^q[/tex] is even, and modulo [tex]q[/tex]
[tex]5^2+5^q\equiv 25+5=30\pmod q\ \Rightarrow\ q\mid 30[/tex]
so [tex]q\in\{2, \,3, \,5\}[/tex], i.e. [tex]q=2[/tex] or [tex]q=3[/tex]. For [tex]q=2[/tex]: [tex]4\nmid 50[/tex], rejected. For [tex]q=3[/tex]: [tex]5^2+5^3=150=6\times 25[/tex], so [tex](2, 3)[/tex] and, by symmetry, [tex](3, 2)[/tex] are solutions.
Case [tex]3[/tex]: [tex]p, q\notin\{2, \,5\}[/tex]. From [tex]p\mid 5^p+5^q[/tex] and [tex]5^p\equiv 5\pmod p[/tex] we get [tex]p\mid 5\left(5^{q-1}+1\right)[/tex], and since [tex]p\ne 5[/tex], [tex]p\mid 5^{q-1}+1[/tex]. In the same way [tex]q\mid 5^{p-1}+1[/tex]:
[tex]5^{q-1}\equiv -1\pmod p,\qquad 5^{p-1}\equiv -1\pmod q[/tex]
Let [tex]d[/tex] be the smallest positive integer with [tex]5^d\equiv 1\pmod p[/tex]; then [tex]5^k\equiv 1\pmod p[/tex] exactly when [tex]d\mid k[/tex]. We have [tex]d\mid p-1[/tex] (by Fermat's theorem), [tex]d\mid 2(q-1)[/tex] (because [tex]5^{2(q-1)}\equiv 1[/tex]) and [tex]d\nmid q-1[/tex] (because [tex]5^{q-1}\equiv -1\not\equiv 1[/tex], as [tex]p\gt 2[/tex]).
Let [tex]2^s[/tex] be the highest power of [tex]2[/tex] dividing [tex]q-1[/tex], and write [tex]d=2^t d'[/tex] with [tex]d'[/tex] odd. From [tex]d\mid 2(q-1)[/tex] we get [tex]d'\mid q-1[/tex] and [tex]t\le s+1[/tex]; if [tex]t\le s[/tex], then [tex]d\mid q-1[/tex], which is false. So [tex]t=s+1[/tex], and since [tex]d\mid p-1[/tex], also [tex]2^{s+1}\mid p-1[/tex]: the exponent of [tex]2[/tex] in [tex]p-1[/tex] is greater than in [tex]q-1[/tex].
Swapping the roles of [tex]p[/tex] and [tex]q[/tex], the exponent of [tex]2[/tex] in [tex]q-1[/tex] is greater than in [tex]p-1[/tex], a contradiction. So this case gives no solutions (including [tex]p=q[/tex]). All solutions:
[tex](2, 3),\ (3, 2),\ (2, 5),\ (5, 2),\ (5, 5),\ (5, 313),\ (313, 5)[/tex]