Brilliant Junior Number Theory Contest (Season 1) ENDS

Nice solution.

Awesome ! nice solution ....

Post next regular problem ...

Solution to Problem 2

Since the 2 questions are so similar, I'll just prove for one case.

From Euler's Theorem,

$2^{10n}\equiv 1\ \left(\operatorname{mod}11\right)$

So,

$2^{2^{4n+1}}\ \equiv 2^{\left[2^{4n+1}\ \left(\operatorname{mod}\ 10\right)\right]}\operatorname{mod}\ 11\$

Using Euler's theorem again,

$2^{4n+1} \equiv 2\ (\operatorname{mod}\ 10)$

Hence

$2^{\left[2^{4n+1}\ \left(\operatorname{mod}\ 10\right)\right]}=4\ (\operatorname{mod}\ 11)$

The result follows, that $2^{2^{4n+1}}+7$ is divisible by 11.

Similarly, you can prove that $2^{2^{6n+2}}+13$ is divisible by $29$.

@Akshat Sharda Can it be solved this way that all primes are of the form 6k + 1 or 6k - 1. Its easy to show that they are not of the either forms and hence they are composite???

Here is my extremely long method to solving this question (First method I found) :P

$\begin{aligned} 8^x + 15^y &= 17^z\\ \Rightarrow 1+1 &\equiv 17^z \pmod{7}\\ \Rightarrow 17^z &\equiv 2 \pmod{7}\\ \Rightarrow z\ &\equiv 2 \pmod{6} \end{aligned}$

Thus, $z$ is even. Also, we have

$\begin{aligned} 8^x + 15^y &= 17^z\\ 8^x &= 17^z - 15^y\\ 0 &= 1^x - (-1)^y \pmod{8}\\ y &= 0 \pmod{2} \end{aligned}$

Thus, $y$ is even. Also, we have (from looking at the equation in $\pmod{10}$), $8^{4a}+15^b = 17^{4c}$ and $8^{4a+2} + 15^b = 17^{4c+2}$. Thus, $x$ is even. Let $x=2x_1$, $y=2y_1$ and $z=2z_1$. Substituting back in, we get

$\begin{aligned} 2^{6x_1} &= 17^{2z_1} - 15^{2y_1}\\ 2^{6x_1} &= (17^{z_1} - 15^{y_1})(17^{z_1} + 15^{y_1}) \end{aligned}$

Because of FTA, we can let $17^{z_1} - 15^{y_1}=2^a$ and $17^{z_1} + 15^{y_1} = 2^b$, with $a + b = 6x_1$ and $a < b$. We now have

$\begin{aligned} 17^{z_1} - 15^{y_1} &= 2^a\\ 17^{z_1} + 15^{y_1} &= 2^b\\ \Rightarrow 17^{y_1} &= 2^{b-1} + 2^{a-1} \end{aligned}$

From this, since the LHS is odd, the RHS must be odd, so $a = 1$ and $b = 6x_1 - 1$. Substituting this, we get

$\begin{aligned} 17^{z_1} - 15^{y_1} &= 2\\ 17^{z_1} + 15^{y_1} &= 2^{6x_1-1}\\ \Rightarrow (-1)^{z_1} + 0 &\equiv -1 \pmod{3}\\ \Rightarrow z_1 &\equiv 1 \pmod{2} \end{aligned}$

$\begin{aligned} 17^{z_1} - 15^{y_1} &= 2\\ 17^{z_1} + 15^{y_1} &= 2^{6x_1-1}\\ \Rightarrow 1^{z_1} - (-1)^{y_1} &\equiv 0 \pmod{8}\\ \Rightarrow y_1 &\equiv 1 \pmod{2} \end{aligned}$

Thus, $y_1$ and $z_1$ are odd, which implies that $x_1$ is odd from $8^{4a+2} + 15^b = 17^{4c+2}$.

Going back to the original equation and substituting $x=4x_2+2$, $y=4y_2+2$ and $z=4z_2+2$, we get

$\begin{aligned} 8^{4x_2+2} + 15^{4y_2+2} = 17^{4z_2+2}\\ 15^{4y_2+2} = (17^{2z_2+1} - 8^{2x_2+1})(17^{2z_2+1} + 8^{2x_2+1}) \end{aligned}$

Once again, by FTA, let $17^{2z_2+1} - 8^{2x_2+1} = 3^a 5^b$ and $17^{2z_2+1} + 8^{2x_2+1}=3^b 5^a$, where $a+b=4y_2+2$.

$\begin{aligned} 17^{2z_2+1} - 8^{2x_2+1}&= 3^a 5^b\\ 17^{2z_2+1} + 8^{2x_2+1}&=3^b 5^a\\ \Rightarrow (-1)^{2z_2+1} + (-1)^{2x_2+1} &\equiv 0 \pmod{3}\\ \Rightarrow (-1)-1 &\equiv 0 \pmod{3} \end{aligned}$

Since this isn't true, we have that $b=0$ so $a=4y_2+2$. We now have

$\begin{aligned} 17^{2z_2+1} - 8^{2x_2+1}&= 9^{2y_2+1}\\ 17^{2z_2+1} + 8^{2x_2+1}&= 25^{2y_2+1} \end{aligned}$

For $x_2 > 0$, we have $8^{2x_2+1} \equiv 0 \pmod{64}$. Also, $17^{2z_2+1} \equiv 17, 49 \pmod{64}$ and $25^{2y_2+1} \equiv 25,9,57,41$. Since both of these terms don't share any residues in $\pmod{64}$, $x_2 = 0$. Substituting this back in to the original equaition, we get

$\begin{aligned} 8^2 + 15^y &= 17^z\\ \Rightarrow 17^{z_1} + 15^{y_1} &= 32\\ 17^{z_1}-15^{y_1} &= 2\\ \Rightarrow 17^{z_1} = 17\\ 15^{y_1} = 15\\ \Rightarrow z_1&=1\\ y_1&=1 \end{aligned}$

Thus, $x=2$, $y=2$, $z=2$ is the only solution.

Are integers x,y,z are different?

Solution to Problem 1

Let us consider,

$\displaystyle \sum_{n=1}^{M}p. \phi(1+p^{n-1}) \leq \displaystyle \sum_{n=1}^{M} p^{n+1}-p^n \\ p \displaystyle \sum_{n=1}^{M} \phi(1+p^{n-1}) \leq (p-1) \displaystyle \sum_{n=1}^{M} p^n \\ p \displaystyle \sum_{n=1}^{M} \phi(1+p^{n-1}) \leq (p-1)\cdot p \cdot \frac{p^m-1}{p-1} \\ \displaystyle \sum_{n=1}^{M} \phi(1+p^{n-1}) \leq p^m-1$

Now, as $p \in \mathbb{N}$, for $p=1$,

$\displaystyle \sum_{n=1}^{M} \phi(1+p^{n-1})=\displaystyle \sum_{n=1}^{M} \phi(1+1^{n-1})=M$

And,

$p^M-1=1^M-1=0$

As $M$ is a natural number it should be obviously more than $0$, but inequality is giving us $M\leq 0$. Thus , it does not hold true.

Let gcd(m,n)=k

Then LCM(m,n) = (mn)/k

(mn/k) + k =m+n

On rearranging, $k^2 -(a+b)k +ab=0$

Thus by quadratic formula, k = a or b

Hence proved.

Here is my long, sort of bashy solution:

Suppose that $d$ is a common factor of $n^5+5$ and $(n+1)^5+5$. Thus, we have the following:

$\begin{aligned} d & \mid (n+1)^5+5 - (n^5+5) = 5n^4 + 10n^3 + 10n^2 + 5n + 1\\ \Rightarrow d & \mid (5(n^5 + 5) - (n - 2)(5n^4 + 10n^3 + 10n^2 + 5n + 1) = 10n^3 + 15n^2 + 9n + 27\\ \Rightarrow d & \mid 4(5n^4 + 10n^3 + 10n^2 + 5n + 1) - (2n-1)(10n^3 + 15n^2 + 9n + 27) = 7n^2-43n-23\\ \Rightarrow d & \mid 98(10n^3 + 15n^2 + 9n + 27) - (140n + 1070)(7n^2-43n-23) = 50112n + 27256\\ \Rightarrow d & \mid 1569507840(7n^2 - 43n - 23) - (219240n - 1466005)(50112n + 27256) = 3858751960\\ \Rightarrow d & \mid 3858751960 \end{aligned}$

The prime factorisation of 3858751960 is $2^3 \cdot 5 \cdot 7 \cdot 1968751$ (you can check the last term is a prime though any means of primality checking).

Since $n^5+5$ and $(n+1)^5+5$ are alternatively odd and even, $2$ cannot be their common factor. Also, by FLT, since $n^5 \equiv n \pmod{5}$, $d$ cannot be equal to 5. By inspection, it can be seen that $n^5$ is not congruent to $(n+1)^5+5$ in $\pmod{7}$. Thus, $d=1$ or $d=1968751$.

We will now find when the $\gcd(n^5+5, (n+1)^5 + 5) > 1$.

Note from above that $d$ must be a common divisor of both $50112n + 27256$ and 1968751. Since 1968751 is a prime, if we have $50112n + 27256 \not \equiv 0 \pmod{1968751}$, we must then have that $d=1$.

Thus, we have $50112n \equiv 1941495 \pmod{1968751}$. We can solve this by finding the modular inverse of 50112. Since 50112 has small factors, we needn't apply Euclid's algorithm. We instead use inspection to find the inverse.

$50112 = 2^6 \cdot 3^3 \cdot 29$. We will now check the value of each factor's inverse in $\pmod{1968751}$.

$\begin{aligned} 2 \times 984376 &= 1968751 + 1\\ \Rightarrow 2^{-1} &\equiv 984376 \pmod{1968751}\\ \Rightarrow 2^{-3} &\equiv 984376 \div 4 =246094 \pmod{1968751}\\ \Rightarrow 2^{-6} &\equiv 246094^2 \equiv 1507325 \pmod{1968751} \end{aligned}$

Similarly, $3^{-3} \equiv 1239584 \pmod{1968751}$ and $29^{-1} \equiv 67888$. Thus, the modular inverse of 50112 is

$50112^{-1} \equiv 2^{-6} \cdot 3^{-3} \cdot 29^{-1} \equiv 1507325 \times 1239584 \times 67888 \equiv 1731811 \pmod{1968751}$

Thus, we have

$\begin{aligned}50112n &\equiv 1941495 \pmod{1968751}\\ n &\equiv 194195 \times 1731811 \equiv 533360 \pmod{1968751} \end{aligned}$

Therefore, when $n \equiv 533360 \pmod{1968751}$, $n^5+5$ and $(n+1)^5+5$ are not coprime.

This problem seems difficult than it looks... I have done half of the proof , just trll me no casework is required isnt it ? At first I tried to provethat by a little Modular Arith. but I am getting stuck in between...I am missing something basic...btw sharky you can arite the solution for shivams problem...This problem has made me crazy...@Sharky Kesa

Solution of problem "extra partecipation problem -set 2: #2" $n^5 + 5$ and $(n+1)^5 + 5$ have no common divisors because seen that $n^5$ and $(n+1)^5$ are coprime for all positive integers $n$ if we add 5 to both they will remain coprime.

Being all the primes $>5$ ends with 1,3,7 or 9 $n$ will end with $0, 8$ or $2$ because it must be in the middle of two primes. So $2|n$and $3|n$* for all $n$ means that $2^2|n^2$and $3^2|n^2$. But seen that n is either 5k (if it ends with 0) or it is $\equiv 2, 8 \pmod{10}$ $n^2$ will be either 5k or $\equiv 4 \pmod{10}$. So adding 16 will make $n^2 \equiv 0 \pmod {10}$ and so $5|n$ or in the case of $n=5k$ it is already $\equiv 0 \pmod {10}$. $720=2^4×3^2×5$ so $n^2(n^2+16)$ can be divided in 2 cases:

1) if $n^2=2^2×3^2×5×?$ and $(n^2+16)=2^2×? => n^2(n^2+16) = 2^4×3^2×5×?$ and so it is divisible by 720.

2) if $n^2=2^2×3^2×?$ and $(n^2+16)=2^2×5×? => n^2(n^2+16) = 2^4×3^2×5×?$ and so it is divisible by 720.

• the proof that $3|n$ is this: In a series of digits from 0 to 9 (we can think like if it is $\pmod{10}$ ) we can have the 0 the 3 the 6 and the 9 wich are divisible by 3. In this case $n$ can't be between 7 and 9 because 9 is not prime and neither between 1 and 3 because 3 is not prime. So it can only be the 0 because 1 is prime and also the 9 of an hypothetical previous series (wich can't be divisible by 3). While if are 2, 5 and 8 divisible by 3 this means that if I take 8 $3|n$ and the same for 2. But I can't take 0 because it is between a 9 which is surely divisible by 3. If 1, 4 and 7 are divisible by 3 my $n$ could only be the 0 between my 9 and the 1 of a next series because 7 and 1 are divisible by 3. And also the next 0 is divisible by 3. In conclusion if we consider the last digit of any numbers we can always refer to this table and so all our $n$ are divisible by 3.

Let $a \ge b$, then we have $a^x \ge b^x$ or $a^x+b^x \ge 2b^x$

This means $2^{y-1} \ge b^x$

Now consider $b \ge a$ then we have $b^x \ge a^x$ or $2b^x \ge a^x+b^x$

This means $b^x \ge 2^{y-1}$

Therefore $b^{x} = 2^{y-1}$

Similarly we can prove $a^x=2^{y-1}$.

Hence we have $a^x=b^x \Longrightarrow a=b$

How much will I get @Sharky Kesa

Solution to Problem 3

This is already a well known problem.

Let,

$n=p_{1}^{a_1}\cdot p_{2}^{a_2}\cdot p_{3}^{a_3}\cdot \ldots \cdot p_{r}^{a_r}$

As $d|n$,

$d=p_{1}^{b_1}\cdot p_{2}^{b_2}\cdot p_{3}^{b_3}\cdot \ldots \cdot p_{r}^{b_r}$

Here, $0 ≤b_i ≤ a_i,\quad i=1,2,\ldots, r$. If $b_i≥2, \quad \mu(d)=0$. Therefore,

\begin{aligned} \displaystyle \sum_{d|n} \mu(d) & =\displaystyle \sum_{\substack{(b_1,b_2, \ldots , b_r) \\ b_i = 0 \text{ or } 1}} \mu( p_{1}^{b_1}\cdot p_{2}^{b_2}\cdot p_{3}^{b_3}\cdot \ldots \cdot p_{r}^{b_r}) \\ &=1 - \binom{r}{1} + \binom{r}{2} - \cdots + (-1)^{r} \binom {r}{r} \\ &= (1 - 1)^{r} \\ &= 0 \end{aligned}

Answer to Problem 4: Using concept of linear recurrence relations we get $x_{n}=\frac{2^{n+1}+(-1)^{n}}{3},y_{n}=2(3)^{n}+(-1)^{n+1}$

Now let $x_{m}=y_{n}$

$2(3^{n+1}-2^{m})=3(-1)^{m}+(-1)^{n}$ $RHS=4,-4,2,-2$ Therefore

$(3^{n+1}-2^{m})$ can be equal to $2,-2,1,-1$

But $LHS=odd$ Since $2^{w}=even,3^{q}=odd$ and $odd-even=odd$.

Therefore $(3^{n+1}-2^{m})=1,-1$ which is possible only for $(m,n)=(0,1)$ while taking the $RHS$ in consideration . Therefore only $x_{0}=y_{1}$ Hence proved .

@Svatejas Shivakumar My solution is this:

What I will be doing is that I show that the expression is divisible by 125 and also by 16.

$121^{n} -25^{n}$ is divisible by 121 - 25 = 96 and hence by 16. Also $1900^{n} - (-4)^{n}$ is divisible by 1900 - (-4) = 1904 and hence by 16. So the expression is divisible by 16.

$1900^{n} - 25^{n}$ is divisible by 1900 - 25 = 1875 and hence by 125. Also $121^{n} - (-4)^{n}$ is divisible by 121 - (-4) = 125. So the whole expression is divisible by 125.

Hence the expression is divisible by $125\times16$...

As a shortcut you can straight away put n = 1 and check....

$121^n-25^n+1900^n-(-4)^n \pmod 2 \\ 1^n-1^n+0-0 \equiv 0 \pmod 2 \\ 121^n-25^n+1900^n-(-4)^n \pmod 5 \\ \underbrace{1^n+0+0-(-4) \equiv 0 \pmod 5}_{n=\text{ odd}} \\ \underbrace{1^n+0+0-(6) \equiv 0 \pmod 5}_{n=\text{ even}}$

Therefore, $121^n-25^n+1900^n-(-4)^n \equiv 0 \pmod {2000}$

I think there's a relatively simpler argument.

For all positive integers $n$, we have,

$(n+1)(n+2)\cdots (2n-1)(2n)=\frac{(2n)!}{n!}=\frac{(2n)!!(2n-1)!!}{n!}=\frac{2^n\cdot n!\cdot (2n-1)!!}{n!}=2^n (2n-1)!!$

which is obviously divisible by $2^n$ for all $n\in\Bbb Z^+$ since $(2n-1)!!$ is an integer for all $n\in\Bbb Z^+$.