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 pp, qq and rr satisfy the following two conditions.

p+q<111andp+qr=pq+r.p + q < 111 \quad \text{and} \quad \dfrac {p+q}{r} = p - q + r.

Find the largest possible value of pqrpqr.

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

x2+y2+z2=22015(x+y+z).x^2 + y^2 + z^2 = 2^{2015} (x + y + z).

3) An example of Clayton's cancelling is 16̸4=14\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 aa, bb and cc to the equation

5a+b2=3c.5^a + b^2 = 3^c.

5) Which positive integers can be written in the form

a2+b2c2a^2 + b^2 - c^2

for positive integers 1a<b<c1 \leq a < b < c?

Note by Sharky Kesa
3 years, 10 months ago

No vote yet
1 vote

  Easy Math Editor

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.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

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 - 3 years, 10 months ago

Log in to reply

Great solution! You would get 7 out of 7. Only 1 improvement is to make your proof look neater (paragraphing, spacing, etc.)

Sharky Kesa - 3 years, 10 months ago

Log in to reply

5a+b2=3c5a+b23=3c1\Large{{ 5 }^{ a }+{ b }^{ 2 }={ 3 }^{ c }\\ \Longrightarrow \frac { { 5 }^{ a }+{ b }^{ 2 } }{ 3 } ={ 3 }^{ c-1 }}

Since 3c13^{c-1} is an integer. We have

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

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

This helps in creating a table for 5a5^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 aa is odd because at odd powers of 5 it leaves remainder 2.

5a+b2=3c5a1=3cb25\Large{{ 5 }^{ a }+{ b }^{ 2 }={ 3 }^{ c }\\ \Longrightarrow { 5 }^{ a-1 }=\frac { { 3 }^{ c }-{ b }^{ 2 } }{ 5 } }

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

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

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

Say a=3a=3 then we have 3c>1253^c > 125, so minimum possible value of cc is 66, but 729125=604729-125=604 is not a perfect square.

By the same we can prove there will be no solutions for a3a \ge 3. This leaves only solution to us as (a,b,c)=(1,2,2) (a,b,c)=(1,2,2).

Department 8 - 3 years, 10 months ago

Log in to reply

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 a3a \geq 3

Sualeh Asif - 3 years, 10 months ago

Log in to reply

Please see it now. Can you help me with the second part

Department 8 - 3 years, 10 months ago

Log in to reply

@Department 8 Check it out^

Sualeh Asif - 3 years, 10 months ago

Log in to reply

@Sualeh Asif Thanks, I am pretty much rookie in maths and writing solutions

Department 8 - 3 years, 10 months 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 5a+b2=3c5^a +b^2= 3^c, cc is always even.
Proof: 3cb20mod53^c -b^2 \equiv 0 \mod{5}
Five cases with b04mod5b \equiv 0-4 mod 5
If, b1;c=4k,kZb \equiv 1; c=4k,k \in \mathbb{Z}
b2;c=4k+2,kZb \equiv 2; c=4k+2,k \in \mathbb{Z}
b3;c=4k+2,kZb \equiv 3; c=4k+2,k \in \mathbb{Z}
b4;c=4k,kZb \equiv 4; c=4k,k \in \mathbb{Z}
b1b \equiv 1 no solutions.
Hence cc is always even. And we are done.

Let c=2mc=2m, 5a=3cb25^a=3^c-b^2
5a=32mb25^a=3^{2m}-b^2
5a=(3mb)(3m+b)5^a=(3^m-b)(3^m +b)
Hence we have two equations:
5l=3mb5^l= 3^m -b 5k=3m+b;l+k=a5^k=3^m +b; l+k=a Solving for 3m3^m and bb, we get b=5k5l2b=\dfrac{5^k -5^l}{2} 3m=5k+5l2(1)3^m=\dfrac{5^k +5^l}{2} \longrightarrow (1) Now note that l<kl<k and also if l,k>1l,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=0l=0 in (1).
We now have to solve this equation for k,mk,m. [3^m =\dfrac{1 +5^k}{2} \longrightarrow (2)) for k,mk,m

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

Lemma 3: There are no solutions to (2) if k>3k>3.
Factoring some the terms, note that k1k-1 is even (and so k2k-2 odd).
3m=(5+1)(5k15k2+5k3+1)23^m= \dfrac{(5+1)(5^{k-1} -5^{k-2}+ 5^{k-3} \cdots +1)}{2}
3m1=(5k15k2)+(5k35k4)++13^{m-1}=(5^{k-1} -5^{k-2})+ (5^{k-3} -5^{k-4})+ \cdots +1
Now see that each of the bracket (5ka5ka1)1mod3(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)+10mod3(-1)+(-1)+(-1)+(-1) \cdots +1 \equiv 0 \mod{3}
Thus, the number of (-1)'s are 1mod3\equiv 1 \mod{3}
k12mod3k-1\equiv 2 \mod{3}
k0mod3k\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:
3m1=5k3(525+1)5k6(525+1)+(525+1)3^{m-1}=5^{k-3}(5^2 -5 +1) -5^{k-6}(5^2 -5 +1)+ \cdots (5^2 -5 +1)
3m1=(525+1)(5k35k6+5k9+1)3^{m-1}=(5^2-5+1)(5^{k-3}-5^{k-6}+5^{k-9}-\cdots +1)
3m1=(21)(5k35k6+5k9+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    a=1k=1, l=0 \implies a=1. This means that 3m=1+512=31    m=1    c=23^m =\dfrac{1 +5^1}{2} =3^1 \implies m=1 \implies c=2 And finally b=2b=2

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


Great Problem! (moving to the next set....)

Sualeh Asif - 3 years, 10 months ago

Log in to reply

You have summoned me. What is it you desire?

Sharky Kesa - 3 years, 10 months ago

Log in to reply

There you go Check it out!

Sualeh Asif - 3 years, 10 months ago

Log in to reply

You may find this helpful.

1664=1664=14 \frac{16}{64} = \frac{1\cancel{6}}{\cancel{6}4}=\frac{1}{4}

Akshat Sharda - 3 years, 10 months ago

Log in to reply

Thanks!

Sharky Kesa - 3 years, 10 months ago

Log in to reply

Another such example

1995=1995=15\frac{19}{95}=\frac{1\cancel{9}}{\cancel{9}5}=\frac{1}{5}

Sachin Sharma - 3 years, 10 months ago

Log in to reply

No, he was referring to crossing the number in LaTeX.

Sharky Kesa - 3 years, 10 months 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 - 3 years, 10 months ago

Log in to reply

You would get 1 out of 7 for this proof. Please re-read the problem to find out where you went wrong.

Sharky Kesa - 3 years, 10 months ago

Log in to reply

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 - 3 years, 10 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 a2+b2c2a^2+b^2-c^2. It does not ask about values of aa, bb and cc.

Sharky Kesa - 3 years, 10 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 - 3 years, 10 months ago

Log in to reply

The question has enough detail and you seem to have misinterpreted it.

Sharky Kesa - 3 years, 10 months ago

Log in to reply

Yes it has enough detail.i was just asking to give required numbers a name :)

Aashirvad Raj - 3 years, 10 months ago

Log in to reply

Actually my english is nt very gud I frequently use wrong words at wrong places ,sry 4 any in convenience :D

Aashirvad Raj - 3 years, 10 months ago

Log in to reply

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

10a+b10b+c=acb=9ac10ac\dfrac{10a+b}{10b+c}=\dfrac{a}{c}\\ \Longrightarrow b=\dfrac{9ac}{10a-c}

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

For a=1a=1

b=9c10cb=\dfrac{9c}{10-c}

By keeping the values of cc from 11 to 99, we get possible pairs as (1,1,1),(1,6,4),(1,9,5) (1,1,1), (1,6,4), (1,9,5) . Applying same methods we find 88 more tuples of a=b=ca=b=c and more solution as (2,6,5),(4,9,8) (2,6,5), (4,9,8) , therefore in total we have 13\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=ca=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

Department 8 - 3 years, 10 months ago

Log in to reply

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 - 3 years, 10 months ago

Log in to reply

Yes I also did it same way. The question 'Anamalous Calculation' is also a similar question. Try it out.

Kushagra Sahni - 3 years, 10 months ago

Log in to reply

You would get 4 out of 7 for this proof. Please re-read the question to see where you went wrong.

Sharky Kesa - 3 years, 10 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...