# 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

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
4 years, 6 months 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:

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.

- 4 years, 6 months ago

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

- 4 years, 6 months ago

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

- 4 years, 6 months ago

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$

- 4 years, 6 months ago

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

- 4 years, 6 months ago

Check it out^

- 4 years, 6 months ago

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

- 4 years, 6 months ago

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

- 4 years, 6 months ago

You have summoned me. What is it you desire?

- 4 years, 6 months ago

There you go Check it out!

- 4 years, 6 months ago

$\frac{16}{64} = \frac{1\cancel{6}}{\cancel{6}4}=\frac{1}{4}$

- 4 years, 6 months ago

Thanks!

- 4 years, 6 months ago

Another such example

$\frac{19}{95}=\frac{1\cancel{9}}{\cancel{9}5}=\frac{1}{5}$

- 4 years, 6 months ago

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

- 4 years, 6 months ago

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

- 4 years, 6 months ago

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

- 4 years, 6 months ago

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

- 4 years, 6 months ago

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

- 4 years, 6 months ago

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 :)

- 4 years, 6 months ago

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

- 4 years, 6 months ago

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

- 4 years, 6 months ago

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

- 4 years, 6 months ago

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

- 4 years, 6 months ago

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.

- 4 years, 6 months ago

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

- 4 years, 6 months ago

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

- 4 years, 6 months ago