# Number Theory Exam Paper

Junior Exam J1

Each question is worth 7 marks.

Time: 4 hours

No books, notes or calculators allowed.

Q1

The sequence

$1, 10, 19, 28, 37, \ldots$

is defined by the rule that a term is the average of its neighbours (excluding the first term).

(a) Prove that $10^{1000}$ is a term in the sequence.

(b) Find the number of times the digit $5$ occurs in the sum of all the terms in the sequence from $1$ to $10^{1000}$.

Q2

$P(n)$ is a function defined as the product of all the factors of $n$. e.g. $P(10) = 1 \cdot 2 \cdot 5 \cdot 10$.

(a) Find all $n$ such that $P(n) = 15n$.

(b) Find all $n$ such that $P(n) = 15n^2$.

Q3

Find all positive integral values of $a$, $b$ and $c$ such that

$a + b = c^2$

$a^2 + b^2 = c^3$

Q4

Find all primes $p$ and $q$ such that

$p^{q + 1} + q^{p + 1}$

is a perfect square. Also state the perfect square.

Q5

Sets $A$ and $B$ contain positive integers such that the sum of any 2 elements in set $A$ are in set $B$ and the quotient (larger element divided by the smaller element) of any 2 elements in set $B$ are in set $A$.

Find the maximum number of elements in $A \cup B$.

Note by Sharky Kesa
6 years, 7 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:

Q2

Let $d_{i}$ be factors of $n$ such that $1 = d_{1} < d_{i} < d_{\sigma_{0}(n)} = n$ for all $1 < i < \sigma_{0}(n)$. ($\sigma_{0}(n)$ is the number of divisors $n$)

The function $P(n)$ becomes

$P(n) = \prod\limits_{i=1}^{\sigma_{0}(n)} d_{i}$

If $n$ is even, we get

$\displaystyle P(n) = d_{1}d_{\sigma_{0}(n)}\times d_{2}d_{\sigma_{0}(n)-1}\times\dots\times d_{\sigma_{0}(n)/2}d_{ \sigma_{0}(n)/2 +1} = n^{\Large \frac{\sigma_{0}(n)}{2}}$

If $n$ is odd, we get

$\displaystyle P(n) = d_{1}d_{\sigma_{0}(n)}\times d_{2}d_{\sigma_{0}(n)-1}\times\dots\times d_{(\sigma_{0}(n)+1)/2 -1}d_{(\sigma_{0}(n)+1)/2 +1}\times (d_{(\sigma_{0}(n)+1)/2}^{2})^{1/2} = n^{\Large \frac{\sigma_{0}(n)-1}{2}}\times n^{\Large \frac{1}{2}} = n^{\Large \frac{\sigma_{0}(n)}{2}}$

For these 2 cases, we get $P(n) = n^{\Large \frac{\sigma_{0}(n)}{2}}$.

(a): $P(n) = 15n$

$n^{\Large \frac{\sigma_{0}(n)}{2}} = 15n$

$n^{\Large \frac{\sigma_{0}(n)-2}{2}} = 15$.

$n^{\sigma_{0}(n)-2} = 225 = 3^{2}\times5^{2}$.

Take $\log$ base $n$ on both sides we get

$\sigma_{0}(n)-2 = 2\times\log_{n}(15)$

Since $\sigma_{0}(n)-2$ is an integer, $2\times\log_{n}(15)$ is also integer.

Which means $n = 15$ or $n = 225$. Check the answers and we get $\boxed{n = 15}$ is the only solution. ~~~!

(b): $P(n) = 15n^{2}$

Similar to (a); we get $\sigma_{0}(n)-4 = 2\times\log_{n}(15)$. But there are no solutions exists in positive integers. ~~~!

- 6 years, 7 months ago

You know there is a much easier solution in terms of appearance.

- 6 years, 7 months ago

What I did is proving the general formula. =w=

- 6 years, 7 months ago

Prob 3: Squaring the first and dividing we get $\dfrac{a^2+2ab+b^2}{a^2+b^2}=1+\dfrac{2ab}{a^2+b^2}=\dfrac{c^4}{c^3}=c$ and so we must have $a^2+b^2\mid 2ab\implies a^2+b^2\le 2ab$. By AM-GM we always have $a^2+b^2\ge 2ab$ so we must have equality, that is $a=b$. Thus $c=2$ giving the only solution $(a,b,c)=(2,2,2)$.

Prob 4: If $p,q > 3$ then $p^{q+1}\equiv q^{p+1}\equiv 1\pmod{3}$ since they are even powers of prime base. So their sum satisfies $p^{q+1}+q^{p+1}\equiv 2\pmod 3$ which is not a quadratic residue mod $3$. So we must have at least one of $p,q\in\{2,3\}$. WLOG we let $p\in\{2,3\}$. If $p=2$ and $q>2$ then $2^{q+1}+q^3=t^2\implies q^3=\left(t+2^{(q+1)/2}\right)\left(t-2^{(q+1)/2}\right)$. So $t+2^{(q+1)/2}=q^i$ and $t-2^{(q+1)/2}=q^j$ so $2^{(q+3)/2}=q^j\left(q^{i-j}-1\right)$ and then $q=2$, a contradiction. On the other hand $(p,q)=(2,2)$ works with square $16$. If $p=3$ then $3^{q+1}+q^4=t^2$ implies $3^{q+1}=\left(t+q^2\right)\left(t-q^2\right)$ so $t+q^2=3^i$ and $t-q^2=3^j$ giving $2q^2=3^j\left(3^{i-j}-1\right)$. Since $q$ is prime, we can easily observe that we must have $j=2$ and $i=3$ so that $q=3$; or $q=2$ and $(i,j)=(2,0)$. We check that none works.

- 6 years, 7 months ago

For problem $4$, you showed that both $p$ and $q$ can't be greater than $3$. Then you concluded that both $p$ and $q$ have to be in $\{2, 3\}$. Do you see what's wrong with that argument?

- 6 years, 7 months ago

Edited.

- 6 years, 7 months ago

$2^{q+1}+q^3\equiv 2\pmod 3$ ?

For $q=5, 2^{q+1}+q^3\equiv 0\pmod 3$.

- 6 years, 7 months ago

Yeah, this fact $p^{q+1}+q^{p+1} \equiv 0 \pmod{3}$ only works for $p,q > 3$. If you choose $p = 2$, this fact doesn't always work for every prime $q$.

- 6 years, 7 months ago

I didn't say that $2^{q+1} + q^3 \equiv 0 \pmod 3$ for all primes $q$. I just showed a counter example @Jubayer Nirjhor 's assumption that $2^{q=1} + q^3 \equiv 2 \pmod 3$.

- 6 years, 7 months ago

Ow, just saw what you edited. Sorry!

- 6 years, 7 months ago

Edited again. Is it OK now?

- 6 years, 7 months ago

Yes. It's OK!

- 6 years, 7 months ago

Q1

(a) Let each term be $a_{n}$. The sequence is defined as $a_{n} = \frac{a_{n-1}+a_{n+1}}{2}$; from this, we know that $a_{n+1} = 2a_{n}-a_{n-1}$.

We can see that $a_{n} = 9n-8$ for base cases $n = 1 = 2$.

$a_{n+1} = 2a_{n}-a_{n-1} = 2(9n-8)-9(n-1)+8$

$= 9(n+1)-8$

Since $10^{1000} \equiv (1+9)^{1000} \equiv 1^{1000} \equiv -8 \mod 9$ and our sequence contains all positive integers of the form $9n-8$, $10^{1000}$ is in our sequence.

(b) Honestly I can't care to do this. I'd be surprised if you had a really elegant solution, but as far as I can tell, it's dealing with nasty repunits.

- 6 years, 7 months ago

I'll tell you that it's very easy to do with arithmetic sum formula.

- 6 years, 7 months ago

Isn't 4 hours a little too generous for this set?

- 6 years, 7 months ago

- 6 years, 7 months ago

To tell you the truth, it was hard enough getting 7 marks in most questions. A couple of them, I made screw ups, even with 4 hours.

- 6 years, 7 months ago