Waste less time on Facebook — follow Brilliant.
×

Australian School of Excellence 2015 Number Theory Exam

  • Each question is worth 7 marks

  • Time allowed is 4 hours

  • No books, notes or calculators permitted

  • Give full proofs with your answers

1) Prime numbers \(p\), \(q\) and \(r\) satisfy the following two conditions.

\[p + q < 111 \quad \text{and} \quad \dfrac {p+q}{r} = p - q + r.\]

Find the largest possible value of \(pqr\).

2) Find all solutions in non-negative integers to the equation

\[x^2 + y^2 + z^2 = 2^{2015} (x + y + z).\]

3) An example of Clayton's cancelling is \(\large \frac { 1\not 6}{\not 64} = \frac {1}{4}\). That is, the correct result is obtained using the incorrect method of "cancelling" the 6s. Find all instances of Clayton's cancelling which simultaneously satisfy the following criteria.

\(\quad\) (i) Both numerator and denominator are strictly two-digit numbers with the numerator smaller than the denominator.

\(\quad\) (ii) The units digit of the numerator is equal to the tens digit of the denominator.

\(\quad\) (iii) Crossing out the units digit of the numerator and the tens digit of the denominator yields the correct lowest terms simplification of the original fraction.

4) Find all solutions in positive integers \(a\), \(b\) and \(c\) to the equation

\[5^a + b^2 = 3^c.\]

5) Which positive integers can be written in the form

\[a^2 + b^2 - c^2\]

for positive integers \(1 \leq a < b < c\)?

Note by Sharky Kesa
12 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

1)If r is an odd prime, let it be of the form 2n+1 where n is a positive integer. If we put this value of r in our equation, we get 2(n+1)q-2np=(2n+1)^2. As L.H.S. is even and R.H.S is odd we won't have any solutions for p,q,r in this case. So r=2. We get 3q-p=4 which means q=(p+4)/3. We can see that q can be an integer when p=2,5,11,17,23,29,41,47,53,59,71,..... After which p+q will exceed 111. So when p is 71 then q is not prime, when p is 59 q is 21 which is again not a prime. But when p is 53, q is 19 which is indeed a prime. So our largest solution set for p,q is 53 and 19 and r=2. So largest possible value of pqr is 53×19×2=2014. Kushagra Sahni · 12 months ago

Log in to reply

@Kushagra Sahni Great solution! You would get 7 out of 7. Only 1 improvement is to make your proof look neater (paragraphing, spacing, etc.) Sharky Kesa · 12 months ago

Log in to reply

Comment deleted 11 months ago

Log in to reply

@Kushagra Sahni What if \(a,b,c=4,5,6\). Right now I am thinking a solution for it. Lakshya Sinha · 11 months, 4 weeks ago

Log in to reply

@Sharky Kesa

Here goes my solutions:

1)Pretty much the same as Kushagra. (though much longer)

4)Lemma 1: In the equation \(5^a +b^2= 3^c\), \(c\) is always even.
Proof: \(3^c -b^2 \equiv 0 \mod{5}\)
Five cases with \(b \equiv 0-4 mod 5\)
If, \(b \equiv 1; c=4k,k \in \mathbb{Z}\)
\(b \equiv 2; c=4k+2,k \in \mathbb{Z}\)
\(b \equiv 3; c=4k+2,k \in \mathbb{Z}\)
\(b \equiv 4; c=4k,k \in \mathbb{Z}\)
\(b \equiv 1\) no solutions.
Hence \(c\) is always even. And we are done.

Let \(c=2m\), \(5^a=3^c-b^2\)
\(5^a=3^{2m}-b^2\)
\(5^a=(3^m-b)(3^m +b)\)
Hence we have two equations:
\[5^l= 3^m -b\] \[5^k=3^m +b; l+k=a\] Solving for \(3^m\) and \(b\), we get \[b=\dfrac{5^k -5^l}{2}\] \[3^m=\dfrac{5^k +5^l}{2} \longrightarrow (1)\] Now note that \(l<k\) and also if \(l,k>1\) then the equation on the right will not be a perfect power of 3, since we could factor out 5 from the equation. Thus we must have \(l=0\) in (1).
We now have to solve this equation for \(k,m\). [3^m =\dfrac{1 +5^k}{2} \longrightarrow (2)) for \(k,m\]

**Lemma 2: \( k\) is odd in (2).**
We have
\(1+5^k \equiv 2 \mod{3}\)
\(5^k \equiv 2 \mod{3}\) If \(k\) is even we have \(5^k \equiv 1 \mod{3}\) by Fermat's little theorem and so for \(k\) odd \(5^k\equiv 2 \mod{3}\) and we are done.

Lemma 3: There are no solutions to (2) if \(k>3\).
Factoring some the terms, note that \(k-1\) is even (and so \(k-2\) odd).
\(3^m= \dfrac{(5+1)(5^{k-1} -5^{k-2}+ 5^{k-3} \cdots +1)}{2}\)
\(3^{m-1}=(5^{k-1} -5^{k-2})+ (5^{k-3} -5^{k-4})+ \cdots +1\)
Now see that each of the bracket \((5^{k-a}-5^{k-a-1}) \equiv -1 \mod{3}\). So you have a stream of (-1)'s followed by a (+1). So since
\((-1)+(-1)+(-1)+(-1) \cdots +1 \equiv 0 \mod{3}\)
Thus, the number of (-1)'s are \(\equiv 1 \mod{3}\)
\(k-1\equiv 2 \mod{3}\)
\(k\equiv 0 \mod 3\)
Our second observation is that k is divisible by 3 along with being odd(Lemma 2). Now group the terms in triplesc(we can since there are k terms) and factor:
\(3^{m-1}=5^{k-3}(5^2 -5 +1) -5^{k-6}(5^2 -5 +1)+ \cdots (5^2 -5 +1)\)
\(3^{m-1}=(5^2-5+1)(5^{k-3}-5^{k-6}+5^{k-9}-\cdots +1)\)
\(3^{m-1}=(21)(5^{k-3}-5^{k-6}+5^{k-9}-\cdots +1)\)
This is a contradiction since The R.H.S is divisible by 7 and the L.H.S is not. And we are done! Q.E.D

Using Lemma 3 we have that (at last) \(k=1, l=0 \implies a=1\). This means that \[3^m =\dfrac{1 +5^1}{2} =3^1 \implies m=1 \implies c=2\] And finally \(b=2\)

Hence the only solution set to \(5^a +b^2= 3^c\) is \((a,b,c) \equiv (1,2,2)\). And we are done.


Great Problem! (moving to the next set....) Sualeh Asif · 11 months, 3 weeks ago

Log in to reply

@Sualeh Asif You have summoned me. What is it you desire? Sharky Kesa · 11 months, 3 weeks ago

Log in to reply

@Sharky Kesa There you go Check it out! Sualeh Asif · 11 months, 3 weeks ago

Log in to reply

\[\Large{{ 5 }^{ a }+{ b }^{ 2 }={ 3 }^{ c }\\ \Longrightarrow \frac { { 5 }^{ a }+{ b }^{ 2 } }{ 3 } ={ 3 }^{ c-1 }}\]

Since \(3^{c-1}\) is an integer. We have

\[{ 5 }^{ a }+{ b }^{ 2 }\equiv 0\quad \left( \mod 3 \right) \]

If \({ b }^{ 2 }\equiv 0\quad \left( \mod 3 \right)\), So \({ 5 }^{ a }\equiv 0\quad \left( \mod 3 \right) \) (this is not possible). So by Fermat's Little theorem \(b^2 \equiv 1 ( \mod 3) \Longrightarrow 5^a \equiv 2 \quad ( \mod 3)\).

This helps in creating a table for \(5^a\):

\[\Large{\underline { \begin{matrix} a & & R \end{matrix} } \\ \begin{matrix} 1 & & 2 \\ 2 & & 1 \\ 3 & & 2 \\ 4 & & 1 \end{matrix} \\ \text{ Here R means the remainder when 5^a is divided by 3} }\]

Clearly \(a\) is odd because at odd powers of 5 it leaves remainder 2.

\[\Large{{ 5 }^{ a }+{ b }^{ 2 }={ 3 }^{ c }\\ \Longrightarrow { 5 }^{ a-1 }=\frac { { 3 }^{ c }-{ b }^{ 2 } }{ 5 } }\]

If \(b^2 \equiv 0 \quad (\mod 5)\), So \( 3^c \equiv 0 \quad ( \mod 5) \) (this is not possible). Hence we create a table for \(3^c\):

\[\Large{\underline { \begin{matrix} c & & R \end{matrix} } \\ \begin{matrix} 1 & & 3 \\ 2 & & 4 \\ 3 & & 2 \\ 4 & & 1 \end{matrix} }\]

Clearly \(c\) must be even because after only this \(3^c \equiv b^2 \quad (\mod 5)\).

Say \(a=3\) then we have \(3^c > 125\), so minimum possible value of \(c\) is \(6\), but \(729-125=604\) is not a perfect square.

By the same we can prove there will be no solutions for \(a \ge 3\). This leaves only solution to us as \( (a,b,c)=(1,2,2)\). Lakshya Sinha · 11 months, 4 weeks ago

Log in to reply

@Lakshya Sinha Several Problems:
1) How do you know that a is always odd, You must prove it.(it is true but proving is necessary)

2) You gave no rigorous proof for \(a \geq 3\) Sualeh Asif · 11 months, 3 weeks ago

Log in to reply

@Sualeh Asif Please see it now. Can you help me with the second part Lakshya Sinha · 11 months, 3 weeks ago

Log in to reply

@Lakshya Sinha Check it out^ Sualeh Asif · 11 months, 3 weeks ago

Log in to reply

@Sualeh Asif Thanks, I am pretty much rookie in maths and writing solutions Lakshya Sinha · 11 months, 3 weeks ago

Log in to reply

Answer to question no. 5 --> if d is the required no. And d=a^2+b^2-c^2 Then a,b,c is set of all triplets a,b,c where a,b,c are sides of an acute angled triangle and c is the largest side EXPLANATION- the given conditions can be manipulated as ●a^2+b^2>c^2 ●a<c ●b<c and this conditions are fullfilled by sides of an acute angled triangle. :D •smallest set of a,b,c is (4,5,6) Which comes just after (3,4,5)the smallest set of primitive pythagorean triplet 3^2+4^2=5^2 4^2+5^2> 6^6 now since we have value of a,b,c we can easily calculate values of d=a^2+b^2-c^2 Where d is the required numbers now for a,b,c(4,5,6) d=5 and so on Aashirvad Raj · 12 months ago

Log in to reply

@Aashirvad Raj You would get 1 out of 7 for this proof. Please re-read the problem to find out where you went wrong. Sharky Kesa · 12 months ago

Log in to reply

@Sharky Kesa Ummm I think I jst forget to add the FORMAL end lines in mt solution.i thought every one will automatically think over it. Check out now! I added last lines. this is my limit I cant think more better sol sry :D Aashirvad Raj · 12 months ago

Log in to reply

@Aashirvad Raj No. You haven't read the question properly. The question asks for all positive integers that can be written in the form \(a^2+b^2-c^2\). It does not ask about values of \(a\), \(b\) and \(c\). Sharky Kesa · 12 months ago

Log in to reply

You may find this helpful.

\(\require{cancel} \frac{16}{64} = \frac{1\cancel{6}}{\cancel{6}4}=\frac{1}{4}\) Akshat Sharda · 12 months ago

Log in to reply

@Akshat Sharda Another such example

\(\require{cancel}\frac{19}{95}=\frac{1\cancel{9}}{\cancel{9}5}=\frac{1}{5}\) Sachin Sharma · 12 months ago

Log in to reply

@Sachin Sharma No, he was referring to crossing the number in LaTeX. Sharky Kesa · 12 months ago

Log in to reply

@Akshat Sharda Thanks! Sharky Kesa · 12 months ago

Log in to reply

Comment deleted 12 months ago

Log in to reply

@Swapnil Das You would get 5 out of 7 for this solution. Please re-read the question to find where you went wrong. Sharky Kesa · 12 months ago

Log in to reply

@Sharky Kesa Sharky on which question did Swapnil write a solution? He deleted the comment so I couldn't figure it out. Kushagra Sahni · 12 months ago

Log in to reply

@Kushagra Sahni He did question 3. Sharky Kesa · 12 months ago

Log in to reply

@Sharky Kesa Hmm.. I would review this again. Swapnil Das · 12 months ago

Log in to reply

Q3) Let the numbers be \(AB=10a+b\) and \(BC=10b+c\). Clearly we have

\[\dfrac{10a+b}{10b+c}=\dfrac{a}{c}\\ \Longrightarrow b=\dfrac{9ac}{10a-c}\]

Since \(b \in \mathbb{Z^{+}}, 9 \ge b \ge 1\), We will make cases for \(a=1,2,3,4,5,6,7,8,9\)

For \(a=1\)

\[b=\dfrac{9c}{10-c}\]

By keeping the values of \(c\) from \(1\) to \(9\), we get possible pairs as \( (1,1,1), (1,6,4), (1,9,5) \). Applying same methods we find \(8\) more tuples of \(a=b=c\) and more solution as \( (2,6,5), (4,9,8) \), therefore in total we have \(\boxed{13}\) solutions.

If you feel my answer is wrong somewhere or you want to make this solution better please feel free to ask or reply me here.

Thank you @Sharky Kesa, since we are given numerator is strictly smaller than denominator so we discard the solutions of \(a=b=c\). This gives only 4 possible solution as mentioned above.

Sharky I am getting only one solution to q4. Am I right? If I am I will post a solution soon Lakshya Sinha · 12 months ago

Log in to reply

@Lakshya Sinha Yes I also did it same way. The question 'Anamalous Calculation' is also a similar question. Try it out. Kushagra Sahni · 11 months, 4 weeks ago

Log in to reply

@Lakshya Sinha Technically, you would get 5 out of 7 for this proof. But it is correct. You just have to put how you got the solutions.

Yes, there is only one solution to q4. Sharky Kesa · 12 months ago

Log in to reply

@Lakshya Sinha You would get 4 out of 7 for this proof. Please re-read the question to see where you went wrong. Sharky Kesa · 12 months ago

Log in to reply

Hey sharky in q no.5 it wud b btr if u 'ill write a^2+b^2-c^2=d ,where d is some positive integer. without it question is not specific :) Aashirvad Raj · 12 months ago

Log in to reply

@Aashirvad Raj The question has enough detail and you seem to have misinterpreted it. Sharky Kesa · 12 months ago

Log in to reply

@Sharky Kesa Actually my english is nt very gud I frequently use wrong words at wrong places ,sry 4 any in convenience :D Aashirvad Raj · 12 months ago

Log in to reply

@Sharky Kesa Yes it has enough detail.i was just asking to give required numbers a name :) Aashirvad Raj · 12 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...