# Brilliant Junior Number Theory Contest (Season 1) ENDS

Hello every Brilliant Mind! This is the first season of Brilliant Sub Junior Number Theory Contest. This contest is for beginners or intermediate ones who want to sharpen their skills of problem-solving in overall Number Theory. .

The aim of this contest is to improve the skill of in the computation in all sorts of problem (of basic level) in Number Theory like Proof problems , Types of Congruences , Theorems related to Modular Arith. etc. by learning from each other and of course to have fun !

Eligibility

People should fulfill either of the 2 following:

1. 16 years or below

2. Minimum level preference : Level 3 in Number Theory .

Eligible people here may participate in this contest.

$\text{The rules are as follows : }$ :

(There is a slight change in the rules of the contest : Now there can be more(2-3) unsolved problems(they are called 'Extra Participation Problem(EPP)) ! , so many people can participate in contest at once ! :) One rule to be noted about these EPP's is that , those problems are to be posted until regular problem is unsolved.For each new unsolved problem , there will be new set of EPP's ! Happy Solving !)

1. I will start by posting the first problem. If there is a user solves it, then they must post a new one.

2. You may only post a solution of the problem below the thread of problem and post your proposed problem in a new thread. Put them separately.

3. Only make substantial comment that will contribute to the discussion.

4. Make sure you know how to solve your own problem before posting it in case there is no one can answer it within 48 hours, then you must post the solution and you have a right to post another problem.

5. If the one who solves the last problem does not post his/her own problem after solving it within a day, then the one who has a right to post a problem is the last solver before him/her.

6. It is NOT compulsory to post original problems. But make sure it has not been posted on brilliant..

$\text{Format your post is as follows :}$

SOLUTION OF PROBLEM xxx (number of problem) :

PROBLEM xxx (number of problem) :

[Name of the solver]

$\text{Topics allowed for the contest are:}$

Proofs related to congruences , Number Theoretic inequalities , Eulers Theorem , Modular Arithmetic , Number Theoretic Functions , Order of an Integer modulo $n$ .

$\text{Things to keep in mind:}$

###### Targeted participants for this contest are beginners .

$\text{You can discuss about the problems on}$ Discussion Channel for BJNTC

Note by A Former Brilliant Member
4 years ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

$d_{1},d_{2},.....d_{2n}$ can be from $1,2,3,4,...,9$ only

$\sum_{j=1}^{n}d_{2j-1}d_{2j}$ is even If

$(1)$ all the $n$ terms are even

$(2)$ the number of odd terms in the sum is even

$d_{2j-1}d_{2j}$ is even if

$(1)$ both $d_{2j-1}d_{2j}$ are even . There are 16 choices for this

$(2)$ one of them is odd the other one is even ; there are $2(5)(4)=40$ choices for this $d_{2j-1}$ could be odd and $d_{2j}$ even or vice versa ).

Note $d_{2j-1}d_{2j}$ is odd for $25$ choices .

For the sum to be even , an even number of such products must be odd . Number of ways in which $k$ of the $n$ terms are odd and the rest are even is $\binom{n}{k}.25^{k}(56)^{n-k}$.

Total sum is even if $k's$ are even .

Total number of ways

$P_{n}=\sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor}\binom{n}{2k}25^{2k}56^{n-2k}$

Here$\lfloor.\rfloor$ represents floor function.

Let $Q_{n}= \sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor}\binom{n}{2k+1}25^{2k+1}56^{n-2k-1}$

$P_{n}+Q_{n}=(56+25)^{n}$

$P_{n}-Q_{n}=(56-25)^{n}$

Hence $\boxed{P_{n}=\frac{81^{n}+31^{n}}{2}}$

- 4 years ago

Nice solution.

- 4 years ago

Awesome ! nice solution ....

Post next regular problem ...

Problem 2

Prove that all numbers in the form $2^{2^{4n+1}}+7$ and $2^{2^{6n+2}}+13$ for $n\in \mathbb{N}$ are composite.

This problem has been solved by Julian Poon.

- 4 years ago

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$.

- 4 years ago

@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???

- 4 years ago

6(8)+1=49 and 6(6)-1=35

49 and 35 are composite.

- 4 years ago

@Akshat Sharda what I meant is that all primes are of the form 6k +- 1 and not that all 6k+-1 are primes

- 4 years ago

Not all primes.... What about 2 and 3?

- 4 years ago

@Akshat Sharda Leaving 2 and 3...I forgot to mention that....Btw Akshat you are in 9 or 10??

- 4 years ago

- 4 years ago

No, because all numbers in the form above are -1, 1 mod 6

- 4 years ago

@Julian Poon O sorry I didn't mark that the numbers above are of the form 6k-1

- 4 years ago

Problem 6

Find all positive integers (with proof) $x,y,z$ such that $8^{x}+15^{y}=17^{z}$

This problem has been solved by Sharky Kesa.

- 4 years ago

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.

- 4 years ago

I think that if we work with modulo 32 or 64 the solution would be shorter. I haven't solved the problem yet but I think that there are some interesting results with it.

I have a similar (and equally long) solution and was hoping for a shorter one but... oh well. By the way, I think you have a typo where $1^{z_1}-(-1)^{y_1}\equiv 0 \operatorname{mod}3$ should be $1^{z_1}-(-1)^{y_1}\equiv 0 \operatorname{mod}4$

- 4 years ago

i have a very short solution to this question using Beals conjecture only if am permited to post it

- 3 years, 12 months ago

Beals conjecture is still technically unproven, otherwise I'd have used that as my solution.

- 3 years, 12 months ago

Are integers x,y,z are different?

- 4 years ago

If they are not different , then first comes pythagoras XD

Problem 1

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

Disprove (without giving examples , give a proof), for natural numbers $M$ and $p$.

This problem has been solved by Akshat Sharda

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.

- 4 years ago

Extra Participation Problem - Set 1 - #3

Let $m,n\in \mathbb {N}$ such that

$\text{lcm}(m,n)+\gcd(m,n)=m+n$

Prove that one of the 2 numbers is divisible by the other.

This problem has been solved by Harsh Shrivastava.

- 4 years ago

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.

- 4 years ago

Extra Participation Problem -Set 2: #2

Are $n^5+5$ and $(n+1)^5+5$ coprime for all positive integers $n$? If not, find all values of $n$ for which this is not true.

- 4 years ago

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.

- 4 years ago

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

I didn't use casework in my solution, mainly just divisibility and congruences. Also, because no one has yet given a solution, I will say that there are values of $n$ such that $\gcd(n^5 + 5, (n+1)^5 + 5) > 1$. @Chinmay Sangawadekar @Alex Spagnoletti

- 4 years ago

Hint 2: You will want to know that 1968751 is a prime number if you wish to solve this. Also, use mainly divisibility laws (if $d \mid a$ and $d \mid b$, then $d \mid (ax+by)$).

- 4 years ago

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.

- 4 years ago

@Alex Spagnoletti That isn't true.Counterexample: $gcd(1,3)=1$ but $gcd(1+5,3+5)=gcd(6,8)=2\neq 1$

Every pair of odd positive integers $a,b$ with $gcd(a,b)=1$ is a counterexample,as $gcd(a+5,b+5)\geq 2$ as both $a+5$ and $b+5$ are even numbers.

- 4 years ago

@Abdur Rehman Zahid, Yes but $3$ is not $1 + 1$ It must be $n$ and $n+1$

- 4 years ago

This is not a correct solution. Just because two numbers are coprime doesnt mean that a constant added to both numbers will keep them both coprime.

- 4 years ago

@Sharky Kesa It is not true for all numbers. But for $n$ and $n+1$ this is true. For example an even number can't be the gcd because they are one even and one odd. A 3k number can't be the gcd because if n is a 3k number 3k + 5 is not a 3k number and n and n+1 can be either one 3k and the other 3k+1( or 3k-1) or they can be both non 3k numbers. In this case adding 5 will make one 3k and the other not. For 5k numbers it's easy to see that if n is 5k, n+5 is also 5k but n+1 is not 5k and so it can't be the gcd. So it's the same for the other numbers and naturally this is the same with $n^5$ and $(n+1)^5$ seen that they are just n and (n+1) 5 times. We can also think to prove this absurdly. If n+5 and (n+1)+5 are not coprime this means that $gcd|n+5$ and $gcd|n+6$ but there is no number > 1 that can divide both a number and that number + 1 I think that this reasoning has no mistakes, but if I have made any mistakes please tell me because I can't find them.

- 4 years ago

But we are referring to 5th power of consecutive numbers, not just consecutive numbers. The fifth power of consecutive numbers aren't consecutive.

- 4 years ago

@Sharky Kesa It's right. But $n^5$ and $( n+1)^5$ are divisibile by n and (n+1) so it is the same. It is like if they are separated but they are always divisible by 2 consecutive numbers. So working modulo n I will have $0 + 5$ and $1+5$. So they are consecutive in this form. (And there is another time the absurd)

- 4 years ago

No, your proof is incorrect. It has no mathematical rigour and is basically just an assumption you have incorrectly talked yourself into.

- 4 years ago

Probably I have made some reasoning mistakes. If no one can find the solution can you post it?

- 4 years ago

What you have done is a hasty generalisation. For example, you look at the odd numbers up to 13. 1 is a square number, 3 is a prime number, 5 is a prime number, 7 is a prime number, 9 is a square number, 11 is a prime number, 13 is a prime number. From this, you conclude that all odd numbers are either prime or square numbers, when 15 is an obvious counter-example.

- 4 years ago

Alternate Solution to Problem 5:
Recursion was my strategy.
Let $S(N) = \sum\limits_{q = 1}^{n} d_{2q -1}\cdot d_{2q}$ where $N$ and $d_i$ are as defined.
Let $f(n)$ denote the number of ways we can find a suitable N of $2n$ digits, that satisfies $S(N) \equiv 0 \text{ mod } 2$.
We need to find a recurrence for $f(n)$.

Now consider $N_0$, which is a number with $2n - 2$ digits.

Now, if $N_0$ has $S(N)$ even, then we need to find $d_{2n - 1}, d_{2n}$ such that their product is even.
Note that the number of $N_0$ here is $f(n - 1)$.
The number of ways to find such $d_{2n - 1}, d_{2n}$ is $f(1) = 56$, by simple casework.

If $N_0$ has $S(N)$ odd, then we need to find $d_{2n - 1}, d_{2n}$such that their product is odd.
The number of the number of $N_0$ here is all the $N_0$ not counted in the case above.
As there are $9^{2n - 2}$ possible numbers totally, and each number must fall in either of these categories, there are $9^{2n - 2} - f(n - 1)$ such $N_0$ here.
The number of ways to find such $d_{2n - 1}, d_{2n}$ is $9^2 - f(1) = 25$.

Then, $f(n) = 56\cdot f(n - 1) + 25 \cdot(9^{2n - 2} - f(n - 1))$ for $n > 1$, and $f(1) = 56$
$\Rightarrow f(n) = 31 \cdot f(n - 1) + 25 \cdot 9^{2n - 2}$

With some juggling,
$f(n) = 31 \cdot f(n - 1) + \dfrac{81^n - 31\cdot 81^{n - 1}}{2}$

Noticing that, $f(1) = 56 = \dfrac{81 + 31}{2}$,

We are motivated to try, $f(n) = \dfrac{81^n + 31^n}{2}$ which satisfies the recurrence as well.

$\therefore f(n) = \dfrac{81^n + 31^n}{2}$

- 4 years ago

Extra Participation Problem Set - 2 - #3

Let $n$ be an integer greater than $6$. Prove that if $n-1$ and $n+1$ are both prime then $n^2(n^2+16)$ is divisible by $720$.

Bonus Prove that the converse is not true.

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.

- 4 years ago

Correct! Here is my approach

Any prime number>3 is of the form $1,5 \pmod6$. Thus $n$ is divisible by $6$ take $n$ as $6m$.

Thus it suffices to prove that $m^2(9m^2+4)$ is divisible by $5$.

We eliminate the case $m \equiv 1,4 \pmod 5$ because then $n-1$ and $n+1$ will be divisible by $5$ respectively(so it won't be prime then).

Checking the cases $m \equiv 0,2,3 \pmod5$ we see that each of the cases satisfies.

Hence proved.

Bonus: Take $n=1440$ the expression is divisible by $720$ but $1441$ is not prime $(11 \times 131)$

It is a shorter proof, I like it. However also $n=258$ makes the expression dibisible by $720$ but $259$ is not prime. If $n$ is divisible by 6 and it ends with 8 , 4 or 0 the expression is satisfied also if $(n + 1)$ or $(n - 1)$ are not prime.

- 4 years ago

Yes. There are many ways to prove a counterexample for the bonus.

Yes. Now I have a question, (I'm new in this kind of constest and I don't know much), should I publish a problem here? Or it is just for those people who solve the regular problems?

- 4 years ago

You should post a problem!

- 4 years ago

Okok. Just give me the time to think about.

- 4 years ago

Problem 8

Let $a$, $b$, $x$ and $y$ be positive integers, with $x>1$. Prove that if $a^x + b^x = 2^y$, then $a=b$.

This question is based off AMO 2016 Q6, but a more general form.

- 4 years ago

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

- 3 years, 12 months ago

You have proven the converse of the problem statement. In the first case, you have proven $2^{y-1} \geq b^x$ if $a \geq b$. In the second case, you have proven $2^{y-1} \leq b^x$ if $a \leq b$. From this, you are saying that if $a=b$, then $b^x = 2^{y-1}$. Similarly, you are saying that $a^x = 2^{y-1}$, from which you get $a^x + b^x = 2^y$ if $a=b$ (This is incorrect of course). In any case, you are trying to prove the converse of the problem statement.

- 3 years, 12 months ago

Problem 3

Prove that

$\sum_{d \mid n}\mu(n)=\begin{cases} 1 \text{ if } n=1 \\ 0 \text{ if }n>1 \end{cases}$

Not original.

This problem has been solved by Akshat Sharda

- 4 years ago

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}

- 4 years ago

Problem 4

Let $\{X_n\}$ and $\{Y_n\}$ denote 2 sequences of integers as follows:

$X_0=X_1=1, X_{n+1}=X_n+2X_{n-1} \\ Y_0=1, Y_1=7, Y_{n+1}=2Y_n+3Y_{n-1}$

Prove that except for 1, there is no other term which occur in both sequences.

Not original.

This problem has been solved by Shivam Jadhav.

- 4 years ago

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 .

- 4 years ago

Extra Participation Problem - Set 1 - #1

Show that for every positive integer $n$,

$121^n-25^n+1900^n-(-4)^n$ is divisible by $2000$.

This problem has been solved by Ankit Kumar Jain and Akshat Sharda.

@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....

- 4 years ago

$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}$

- 4 years ago

Can you please explain how you concluded that it is divisible by 2000(last step)?

This is where the Chinese Remainder theorem comes in.

- 4 years ago

Extra Participation Problem - Set 1 - #4

Prove that $(n+1)(n+2) \ldots (2n-1)(2n)$ is divisible by $2^{n}$.

- 4 years ago

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^+$.

Notation: $n!!$ denotes the double factorial.

- 4 years ago

Solution to Extra Participation Problem-Set 1-#4

Here , we know that , $(n+1)(n+2)...(2n-1)(2n) \equiv 0 \mod 2$ , now multiplying the whole congruence by ,

$2^{n-1}$ , we get , $2^{n-1}(n+1)(n+2)...(2n-1)(2n) \equiv 0 \mod 2^n$ , so from here , we know that , $2^{n}$

does not divide $2^{n-1}$ but still remainder is 0 , so it is obvious that , $2^{n} \mid (n+1)(n+2)...(2n-1)(2n)$

How do you conclude that since $2^n\not\mid 2^{n-1}$, we must have $2^n\mid \prod\limits_{i=1}^n (n+i)$ ? Consider $a=2^4~,~b=2^3~,~c=2$, we have $a\mid bc$ and $a\not\mid b$ but that doesn't imply $a\mid c$.

- 4 years ago

Extra Participation Problem- Set 1 - #6

Prove that when $n \in \mathbb{Z^{+}}, n \not=1$, and $2^n + n^2$ is prime, then $n\equiv 3\pmod{6}$.

This problem is not original.

This problem has been solved by Svatejas Shivakumar.

- 4 years ago

If a numbers is a prime number >3, it is $\equiv 1,5 \pmod6$
So, $2^n+n^2 \equiv 1,5 \pmod 6$ for $n \neq 1$