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:

16 years or below

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 !)**

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

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.

Only make substantial comment that will contribute to the discussion.

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.

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.

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

Please post your solution and your proposed problem in a single new thread.

\(\text{Format your post is as follows :}\)

**SOLUTION OF PROBLEM xxx (number of problem) :**

**[Post your solution here]**

**PROBLEM xxx (number of problem) :**

**[Post your problem here]**]]

**[Name of the solver]**

The comments will be easiest to follow if you sort by "Newest":

\(\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:}\)

###### You may include other pure NT topics.

###### Try to avoid toughest problems , such as problems related to Dirichlet's Convolution etc. as this is Junior Contest , the second season will be totally reserved for hard and toughest problems which community will enjoy .

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

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

## Comments

Sort by:

TopNewest\(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}}\] – Shivam Jadhav · 12 months ago

Log in to reply

– Sharky Kesa · 12 months ago

Nice solution.Log in to reply

– Chinmay Sangawadekar · 12 months ago

Post next regular problem ...Log in to reply

– Chinmay Sangawadekar · 12 months ago

Awesome ! nice solution ....Log in to reply

Problem 6Find all positive integers (with proof) \(x,y,z\) such that \[8^{x}+15^{y}=17^{z}\]

This problem has been solved by Sharky Kesa.– Shivam Jadhav · 12 months agoLog in to reply

\[\begin{align} 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{align}\]

Thus, \(z\) is even. Also, we have

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

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{align} 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{align}\]

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{align} 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{align}\]

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{align} 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{align}\]

\[\begin{align} 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{align}\]

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{align} 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{align}\]

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{align} 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{align}\]

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

\[\begin{align} 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{align}\]

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{align} 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{align}\]

Thus, \(x=2\), \(y=2\), \(z=2\) is the only solution. – Sharky Kesa · 12 months ago

Log in to reply

– Svatejas Shivakumar · 12 months 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.Log in to reply

– Benjamin Ononogbu · 11 months, 4 weeks ago

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

– Sharky Kesa · 11 months, 4 weeks ago

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

– Julian Poon · 12 months ago

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\)Log in to reply

– Akshat Sharda · 12 months ago

Are integers x,y,z are different?Log in to reply

– Chinmay Sangawadekar · 12 months ago

If they are not different , then first comes pythagoras XDLog in to reply

– Chinmay Sangawadekar · 12 months ago

thats what i asked him ....Log in to reply

Problem 2Prove 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.– Akshat Sharda · 1 year agoLog in to reply

Solution to Problem 2Since 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\). – Julian Poon · 1 year ago

Log in to reply

@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??? – Ankit Kumar Jain · 12 months ago

Log in to reply

– Julian Poon · 12 months ago

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

@Julian Poon O sorry I didn't mark that the numbers above are of the form 6k-1 – Ankit Kumar Jain · 12 months ago

Log in to reply

49 and 35 are composite. – Akshat Sharda · 12 months ago

Log in to reply

@Akshat Sharda what I meant is that all primes are of the form 6k +- 1 and not that all 6k+-1 are primes – Ankit Kumar Jain · 12 months ago

Log in to reply

– Akshat Sharda · 12 months ago

Not all primes.... What about 2 and 3?Log in to reply

@Akshat Sharda Leaving 2 and 3...I forgot to mention that....Btw Akshat you are in 9 or 10?? – Ankit Kumar Jain · 12 months ago

Log in to reply

– Akshat Sharda · 12 months ago

I'm in 10th grade.Log in to reply

Problem 8Let \(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. – Sharky Kesa · 12 months ago

Log in to reply

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 – Lakshya Sinha · 11 months, 3 weeks ago

Log in to reply

– Sharky Kesa · 11 months, 3 weeks 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.Log in to reply

Extra Participation Problem Set - 2 - #3Let \(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\).

BonusProve that the converse is not true. – Svatejas Shivakumar · 12 months agoLog in to reply

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.

Log in to reply

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)\) – Svatejas Shivakumar · 12 months ago

Log in to reply

– Alex Spagnoletti · 12 months ago

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.Log in to reply

– Svatejas Shivakumar · 12 months ago

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

– Alex Spagnoletti · 12 months ago

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?Log in to reply

– Akshat Sharda · 12 months ago

You should post a problem!Log in to reply

– Alex Spagnoletti · 12 months ago

Okok. Just give me the time to think about.Log in to reply

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} \] – Ameya Daigavane · 12 months ago

Log in to reply

Extra Participation Problem -Set 2: #2Are \(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. – Sharky Kesa · 12 months ago

Log in to reply

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

\[\begin{align} 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{align}\]

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{align} 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{align}\]

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{align}50112n &\equiv 1941495 \pmod{1968751}\\ n &\equiv 194195 \times 1731811 \equiv 533360 \pmod{1968751} \end{align}\]

Therefore, when \(n \equiv 533360 \pmod{1968751}\), \(n^5+5\) and \((n+1)^5+5\) are not coprime. – Sharky Kesa · 12 months ago

Log in to reply

@Sharky Kesa – Chinmay Sangawadekar · 12 months 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...Log in to reply

@Chinmay Sangawadekar @Alex Spagnoletti – Sharky Kesa · 12 months ago

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\).Log in to reply

– Sharky Kesa · 12 months 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)\)).Log in to reply

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. – Alex Spagnoletti · 12 months agoLog in to reply

– Sharky Kesa · 12 months 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.Log in to reply

@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. – Alex Spagnoletti · 12 months ago

Log in to reply

– Sharky Kesa · 12 months ago

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

@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) – Alex Spagnoletti · 12 months ago

Log in to reply

– Sharky Kesa · 12 months ago

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

– Alex Spagnoletti · 12 months ago

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

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. – Sharky Kesa · 12 months agoLog in to reply

@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. – Abdur Rehman Zahid · 12 months ago

Log in to reply

@Abdur Rehman Zahid, Yes but \( 3 \) is not \(1 + 1\) It must be \(n\) and \(n+1\) – Alex Spagnoletti · 12 months ago

Log in to reply

Extra Participation Problem - Set 1 - #3Let \(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.– Akshat Sharda · 12 months agoLog in to reply

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. – Harsh Shrivastava · 12 months ago

Log in to reply

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– Chinmay Sangawadekar · 1 year agoLog in to reply

Solution to Problem 1Let 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. – Akshat Sharda · 1 year ago

Log in to reply

Problem 7Which positive integers can be written in the form

\[x^2 + y^2 - z^2\]

for positive integers \(1 \leq x < y < z\)? – Sharky Kesa · 12 months ago

Log in to reply

I want to prove that all positive integers can be expressed in this form by giving a construction. Let \(m\) be the positive integer which is expressed in this form. We have

\[\begin{align} x^2 + y^2 - z^2 &= m\\ x^2-m&=(z+y)(z-y) \end{align}\]

Let \(z-y=1\). We then must have \(z+y=x^2-m\). Solving this pair of linear equations, we get \(y=\dfrac{x^2-m-1}{2}\) and \(z=\dfrac {x^2-m+1}{2}\). We now want both numerators to be even for all values of \(m\) by finding a suitable expression for \(x\) in terms of \(m\). If we let \(x=m+k\) (for some odd number \(k\)), this would satisfy the numerators being even for all values of \(x\). However, we must also satisfy that \(1 \leq x < y < z\). However, we already have \(y < z\). Let us substitute this expression to find a bound for \(k\).

\[\begin{align} x &< y\\ m+k &< \dfrac{(m + k)^2-k-1}{2}\\ 2m+2k &< m^2+2km+k^2-k-1\\ 2m &< m^2 + 2km + k^2 - 3k - 1 \end{align}\]

Notice how we want to keep \(k^2 - 3k - 1\) positive? Thus, we must have \(k > 3\). The smallest odd value that satisfies is \(k=5\). We can use this for our construction. Thus, our construction is

\[\begin{align} x &= m+5\\ y &= \dfrac {m^2 + 9m + 24}{2}\\ z &= \dfrac {m^2 + 9m + 26}{2} \end{align}\]

Verifying, we get

\[\begin{align} x^2 + y^2 - z^2 &= m\\ (m+5)^2 + \dfrac{(m^2 + 9m+24)^2}{4} - \dfrac{(m^2+9m+26)^2}{4} &= m\\ m^2 + 10m+25 - (m^2 + 9m + 25) &= m\\ m &= m \end{align}\]

Thus, our construction is finished and we have proved that all positive integer can be formed using this construction. – Sharky Kesa · 11 months, 4 weeks ago

Log in to reply

– Svatejas Shivakumar · 12 months ago

Please post the solution.Log in to reply

\( x_{n}= x_{n-1}+ 7 + 2(n-1)\\ x_{0}=5\\ \)

So if \( a=(n+1)(n+5)\) \(a\) can be written in the form \( x^2 + y^2 - z^2\)

However probably there are also other numbers, but there are infinite numbers. – Alex Spagnoletti · 12 months ago

Log in to reply

– Chinmay Sangawadekar · 12 months ago

Exactly same approach I had in my mind...Nice solution ...:) :)Log in to reply

– Alex Spagnoletti · 12 months ago

Thank you :)Log in to reply

– Sharky Kesa · 12 months ago

This is not a complete solution, but a good try. Try again, you are close to the answer.Log in to reply

– Alex Spagnoletti · 12 months ago

After some reasoning I realized that seen that there are infinite combinations of \(x^2 + y^2 - z^2\) also infinite numbers can be generated. And generalizing\(a=(n+1)(n+5)\) I wrote \(a=n(n+α)\) where \(α>-n\). With this every positive number can be generated. Now I'm not sure of this generalization, but at the moment is the only explaination I can find.Log in to reply

– Sharky Kesa · 12 months ago

I'll write up the solution ASAP.Log in to reply

– Alex Spagnoletti · 12 months ago

I have already written a problem for another question I solved so now maybe I will find another one. But should I name them "EPP" or normal problems?Log in to reply

– Svatejas Shivakumar · 12 months ago

EPP set 3 #2Log in to reply

– Alex Spagnoletti · 11 months, 4 weeks ago

ok got it. and when a problem should be named as regular problem?Log in to reply

Extra Participation Problem - set 2 -#1Prove that \(9 \mid \left((7^{n}+1)^{n} - 2^{n}\right)^{3}\) ,for all positive integers \(n\)

This problem has been solved by Sharky K– Chinmay Sangawadekar · 12 months agoLog in to reply

Thus, \(3 \mid (7^n+1)^n - 2^n\), which implies \(27|((7^n+1)^n-2^n)^3\), so 9 divides the expression. Thus proven. – Sharky Kesa · 12 months ago

Log in to reply

– Chinmay Sangawadekar · 12 months ago

Yep !Log in to reply

Extra Participation Problem- Set 1 - #6Prove 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.– Ralph James · 12 months agoLog in to reply

Solution to Extra Participation Problem - Set 1 - #6If 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\)

If \(n \equiv 0 \pmod6\), \(2^n+n^2 \equiv 0 \pmod6\)

If \(n \equiv 1 \pmod6\), \(2^n+n^2 \equiv 3 \pmod6\)

If \(n \equiv 2 \pmod6\), \(2^n+n^2 \equiv 2 \pmod6\)

If \(n \equiv 3 \pmod6\), \(2^n+n^2 \equiv 5 \pmod6\)

If \(n \equiv 4 \pmod6\), \(2^n+n^2 \equiv 2 \pmod6\)

If \(n \equiv 5 \pmod6\), \(2^n+n^2 \equiv 3 \pmod6\)

Only the fourth case is possible.

Hence if \(2^n+n^2\) is prime, then \(n \equiv 3 \pmod6\) – Svatejas Shivakumar · 12 months ago

Log in to reply

Extra Participation Problem - Set 1 - #4Prove that \[(n+1)(n+2) \ldots (2n-1)(2n)\] is divisible by \(2^{n}\). – Harsh Shrivastava · 12 months ago

Log in to reply

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. – Prasun Biswas · 12 months agoLog in to reply

Solution to Extra Participation Problem-Set 1-#4Here , 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)\) – Chinmay Sangawadekar · 12 months ago

Log in to reply

– Prasun Biswas · 12 months ago

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\).Log in to reply

Extra Participation Problem - Set 1 - #1Show 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 · 12 months agoLog in to reply

@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.... – Ankit Kumar Jain · 12 months ago

Log in to reply

Therefore, \[121^n-25^n+1900^n-(-4)^n \equiv 0 \pmod {2000}\] – Akshat Sharda · 12 months ago

Log in to reply

– Svatejas Shivakumar · 12 months ago

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

– Akshat Sharda · 12 months ago

This is where the Chinese Remainder theorem comes in.Log in to reply

Log in to reply

– Sharky Kesa · 12 months ago

Your last line is incorrect. Please read what Svatejas has said. Ankit Kumar Jain has the correct solution.Log in to reply

Log in to reply

Suppose you have a congruence,

\( ac \equiv bc \pmod{n} \)

Then,

\( a \equiv b \pmod{d} \) where \( d = gcd(n,c) \) – Vighnesh Shenoy · 12 months ago

Log in to reply

Problem 4Let \(\{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.– Akshat Sharda · 1 year agoLog in to reply

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 . – Shivam Jadhav · 1 year ago

Log in to reply

Problem 3Prove 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– Julian Poon · 1 year agoLog in to reply

Solution to Problem 3This 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{equation} \begin{split} \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{split} \end{equation} \] – Akshat Sharda · 1 year ago

Log in to reply

Extra Participation Problem Set - 2 - #4Prove that if \(x^2 \equiv a \pmod p\) with \(p\) prime and \(>3\) there are only 2 solutions which are \(s+r=p\).

This problem has been solved by Sharky Kesa.– Alex Spagnoletti · 12 months agoLog in to reply

– Svatejas Shivakumar · 12 months ago

What is s and r and what are we supposed to solve?Log in to reply

So why the solutions are \(r\) and \(s=p-r\) and prove that there are only this 2 solutions. – Alex Spagnoletti · 11 months, 4 weeks ago

Log in to reply

We will prove that if \(x^2 \equiv a \pmod{p}\), then \((p-x)^2 \equiv a \pmod{p}\) (By proving this, we get that the sum of the two values is \(p\).

Let \(x^2 \equiv a \pmod{p}\). We have

\[\begin{align} (p-x)^2 &\equiv p^2 - 2px + x^2 &\pmod{p}\\ &\equiv x^2 &\pmod{p}\\ &\equiv a &\pmod{p} \end{align}\]

Thus, we have that if there are 2 solutions, then their sum is indeed \(p\) and the two solutions are \(s=x\) and \(r=p-x\). We will now prove that there are only 2 solutions. Let \(t^2 \equiv a \pmod{p}\) where \(t \neq x, p-x\) and \(0 < t < p\). We have

\[\begin{align} t^2 &\equiv a \pmod{p}\\ x^2 - t^2 &\equiv 0 \pmod{p}\\ (x-t)(x+t) &\equiv 0 \pmod{p} \end{align}\]

Thus, either \(p \mid x-t\) or \(p \mid x+t\). If \(p \mid x-t\) and \(0 < x,t < p\), we have that \(x-t = 0\), which implies \(x=t\), which contradicts our first statement that \(t \neq x\). If \(p \mid x+t\) and \(0 < x,t < p\), we have that \(x+t = p\), which implies \(t = p-x\), which contradicts our first statement that \(t \neq p-x\). Thus, no such \(t\) exists.

We have proven there exist only 2 values for \(x\) such that \(x^2 \equiv a \pmod{p}\), and that the sum of these two values is \(p\). – Sharky Kesa · 11 months, 4 weeks ago

Log in to reply

– Alex Spagnoletti · 11 months, 4 weeks ago

Yes, it's exactly my proof. Obviously seen that the 2 solutions are \(s+r=p\) they are less than \(p\).Log in to reply

Extra Participation Problem-Set 1 - #5Show that , \(1000!\) terminates in \(249\) zeroes. – Chinmay Sangawadekar · 12 months ago

Log in to reply

The formula for trailing zeroes is: \(\displaystyle\sum_{i=1}^k \left\lfloor\frac{n}{5^i}\right\rfloor \), such that \(5^{k + 1} > n\).

\[5^5 = 3125 > 1000 \implies k = 4\].

\[\left\lfloor\frac{1000}{5^4}\right\rfloor+\left\lfloor\frac{1000}{5^3}\right\rfloor+\left\lfloor\frac{1000}{5^2}\right\rfloor+\left\lfloor\frac{1000}{5^1}\right\rfloor = 1 + 8 + 40 + 200 = \boxed{249}\]. – Ralph James · 12 months ago

Log in to reply

Extra Participation Problem - Set 1 - #2For any integer \(n \geq3\) , prove that , \[\sum_{k=1}^{n}\mu(k!)=1\]

This problem has been solved by Akshat.S– Chinmay Sangawadekar · 12 months agoLog in to reply

Therefore,

\[\displaystyle \sum_{k=1}^{n }\mu(k!) , \quad \forall n ≥3 \\ =\sum_{k=1}^{3}\mu (k!)=\mu(1)+\mu(2)+\mu(3)=1+(-1)^1+(-1)^1=1\] – Akshat Sharda · 12 months ago

Log in to reply

Extra Participation Problem Set 3: #3Let \(m=\dfrac{4^p-1}{3}\), where \(p\) is a prime number exceeding \(3\). Prove that \(2^{m-1}\) has remainder \(1\) when divided by \(m\). – Svatejas Shivakumar · 11 months, 3 weeks ago

Log in to reply

– Chinmay Sangawadekar · 11 months, 2 weeks ago

Svatejas's problem is still unsolved.... May be we should discuss about it in next season...Log in to reply

– Alex Spagnoletti · 11 months, 2 weeks ago

Yes, I think it's betterLog in to reply

– Alex Spagnoletti · 11 months, 3 weeks ago

I think I have found something. First we can notice that \(m-1\) is always divisible by a certain \(k\) which is 2 times \(p\). Then the \({ord}_m(2)\) is k so \(2^{k×h} \equiv 1 \pmod m\). Being \( m-1 \)divisible by \(k\) \(2^{m-1}\) will be \( \equiv 1 \pmod m\).Log in to reply

– Chinmay Sangawadekar · 11 months, 3 weeks ago

First I thought if we prove m is prime then this problem gets proved but that was wrong...later I tried something to do with parity of m ' then rearrangements of congruences etc....but still not able to get the key operation :( have you gotanything else ?Log in to reply

– Alex Spagnoletti · 11 months, 3 weeks ago

No :( the only thing is that m-1 is divisible by \(2p\) and that \(2p\) is also the \(ord_m(2)\)Log in to reply

– Chinmay Sangawadekar · 11 months, 3 weeks ago

M is divisible by 2p is absolutely correct...well your solution seems reasonable and correct.....post it ..and our contest will come to an end....in 1-2 days I will post season 2 please do participate in that ...Log in to reply

– Alex Spagnoletti · 11 months, 3 weeks ago

Yes, I have just to find a formal proof because at the moment I don't know why the \(ord_m(2)\) is 2pLog in to reply

– Chinmay Sangawadekar · 11 months, 3 weeks ago

Lets work on it together... BTW are you a moderator ? Let's work on that proof...Log in to reply

– Alex Spagnoletti · 11 months, 3 weeks ago

No I'm not a moderator. Anyway from where we could begin to prove that?Log in to reply

– Chinmay Sangawadekar · 11 months, 3 weeks ago

Do we need to right proof for m divisible by 2p as this result is pretty obvious...I think we can ask Sharky for our help..if we 3 work on that that will also be easy for us...Log in to reply

– Alex Spagnoletti · 11 months, 3 weeks ago

Yes, I agreeLog in to reply

Log in to reply

– Alex Spagnoletti · 11 months, 3 weeks ago

This is not true. For example 341 is not prime. But it is \((4^5-1)/3\)Log in to reply

– Chinmay Sangawadekar · 11 months, 3 weeks ago

Ohhhh so silly of me... Sorry for that solution.., I will post the correct one sorry again :(Log in to reply

– Alex Spagnoletti · 11 months, 3 weeks ago

Don't worry. I do this kind of mistakes very frequently.Log in to reply

Extra Participation Problem Set 3: #2In how many ways can \(50!\) be written as the sum of 2 or more consecutive numbers? – Sharky Kesa · 11 months, 4 weeks ago

Log in to reply

So \(\dfrac{2 \times 50!+n(1-n)}{2n}=x\) so \(n|50!\) and \(2|1-n\).

So we have to find the number of odd numbers that divides \(50!\)

The prime(except 2) factorization of \(50!\) is \(3^{22} \times 5^{12} \times 7^8 \times 11^4 \times 13^3 \times 17^2 \times 19^2 \times 23^2 \times 29 \times 31 \times 37 \times 41 \times 43 \times 47\)

So the number of odd numbers that divides \(50!\) is \(23 \times 13 \times 9 \times 5 \times 4 \times 3 \times 3 \times 3 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2=\boxed{93000960}\) – Svatejas Shivakumar · 11 months, 4 weeks ago

Log in to reply

– Sharky Kesa · 11 months, 4 weeks ago

Set 2 - Problem 5. Did we finish that set?Log in to reply

Log in to reply

– Sharky Kesa · 11 months, 4 weeks ago

K, fixed it up. You can post next prob then.Log in to reply

Log in to reply

– Sharky Kesa · 11 months, 3 weeks ago

Yeah, but you just have to justify why you have to find the number of odd numbers that divide \(50!\).Log in to reply

– Alex Spagnoletti · 11 months, 3 weeks ago

I don't know if it's right but I justified this because if we divide \(50!\) by an odd number we obtain an odd number of identical parts and so we can take one of them and then remove 1 from one part and add to one other so we obtain parts wich are consecutive and their sum is equal to \(50!\). Ex. \( 15/3=5 \) \( 4+5+6=15\) I removed 1 from the first and add it at the last part. With an even number this is not possible.Log in to reply

When writing a formal proof, you have to justify this by proving this lemma. – Sharky Kesa · 11 months, 3 weeks ago

Log in to reply

– Alex Spagnoletti · 11 months, 3 weeks ago

You did not divide 10 by an odd number. I mean that if our number is of the form \(d×n\) with d odd I will have \(n+n+n...+n\) an odd number of time, so I will have a central n and the others can be written as consecutive numbers with n as central term. About the proof at the moment I have no time to think about.Log in to reply

– Svatejas Shivakumar · 11 months, 3 weeks ago

because 2|1-n which is possible only when n is odd.Log in to reply

Extra Participation Problem Set - 3 - #1Find the smallest value of \(n\) such that the arithmetic mean of the sequence \(1^2,2^2,\ldots,n^2\) is itself a perfect square. – Svatejas Shivakumar · 11 months, 4 weeks ago

Log in to reply

\[\begin{align} \dfrac {n(n+1)(2n+1)}{6n} &= k^2\\ 2n^2+3n+1 &= 6k^2\\ n &= \dfrac {-3 \pm \sqrt{9 + 48k^2 - 8}}{2}\\ n &= \dfrac {-3 \pm \sqrt{48k^2+1}}{2}\\ \end{align}\]

We need to find the smallest value of \(k\) such that \(48k^2 + 1\) is a perfect square, an \(k > 1\). This is just a Pell's equation, which has solutions for

\[48k^2 + 1 = x^2\]

as

\[(x, k) = (7, 1), (97, 14), (1351, 195), \ldots\]

The second solution gives fractional \(n\) and the third solution gives \(n=337\). Thus, \(n=337\) is the smallest solution \(> 1\). – Sharky Kesa · 11 months, 4 weeks ago

Log in to reply

– Alex Spagnoletti · 11 months, 4 weeks ago

I've already done this exercise on brilliant. The answer is \( 337 \) if I remember well.Log in to reply

Problem 5Let \(N\) be a \(2n\) digit number with digits \(d_{1},d_{2},d_{3},...,d_{2n}\) from left to right \(i.e\) \(N= \overline {d_{1}d_{2}....d_{2n}}\) where \(d_{p}\) is not equal to \(0\) , \(p=1,2,...,2n\). Find the number of such \(N\) so that the sum \[\sum_{q=1}^{n}d_{2q-1} \times d_{2q}=even\] in terms of \(n\) . – Shivam Jadhav · 1 year ago

Log in to reply

– Svatejas Shivakumar · 1 year ago

It seems more like a combinatorics problem.Log in to reply

– Shivam Jadhav · 12 months ago

Number theory + CombinatoricsLog in to reply

Log in to reply

Log in to reply

Log in to reply

– Sharky Kesa · 12 months ago

Can you give a rigorous proof why this works?Log in to reply

– Lakshya Sinha · 12 months ago

actually this is based on observationsLog in to reply

– Sharky Kesa · 12 months ago

So, how can we tell that this pattern doesn't break down after 248746 terms (as an example)?Log in to reply

– Lakshya Sinha · 12 months ago

I cannot explain like that but if you take N then I have proved at least n digits should be evenLog in to reply

– Sharky Kesa · 12 months ago

Perhaps you could construct an inductive proof why this works?Log in to reply

@Shivam Jadhav don't post the solution – Lakshya Sinha · 12 months ago

Maybe I will share the solution tommorow so pleaseLog in to reply

– Ameya Daigavane · 12 months ago

Guys I got the solution! Don't post it please!Log in to reply

– Chinmay Sangawadekar · 12 months ago

That problem is done already .... please do discussion here https://brilliant.org/discussions/thread/discussion-channel-for-brilliant-junior-nt-contest/?ref_id=1154816#comment-a3f5109548e92Log in to reply

\[\large{\sum _{ q=1 }^{ n }{ { d }_{ 2q-1 }\times { d }_{ 2q } } =2k}\]

So clearly that when \(N\) is taken in groups of 2 like \(d_{1}\times d_{2}, d_{3}\times d_{4},....\) this means at least one of them is even in the partition so at least \(n\) of them is even.

Consider when \(n=1\):

Let the first digit ( \(d_{1}\) ) be even and the other be from 1 to 9, so we get total possibility of \(4 \times 9\).

Let the second digit be ( \(d_{2}\) ) be even then we again get a total possibility of \(4 \times 9\). Adding them we get \( 72 = (4^{1} \times 9^1) \times 2\). But if we carefully look we will find out that we have counted an extra case of number when all digits are same and even. Since we are looking numbers ranging from 11 to 99 in this case we have to find all numbers that have same digit and are even.

This means it should be the multiple of \(22\) hence total numbers are \(\left\lfloor \dfrac { 99 }{ 22 } \right\rfloor =4\). So total cases are \(72-4=68=2(36^1 \times 1 -2)\)

Similarly for

\( n=2\) we get \( 2(36^2 \times 2 -2)\)

\(n=3\) we get \(2(36^3 \times 3 -2)\).

At the end we see the general pattern is \( \boxed{2(36^n \times n -2)} \). – Lakshya Sinha · 12 months ago

Log in to reply