Number Theory Exam Paper

Junior Exam J1

Each question is worth 7 marks.

Time: 4 hours

No books, notes or calculators allowed.

Note: You must prove your answer.

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

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

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

$a + b = c^2$

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

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

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

is a perfect square. Also state the perfect square.

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

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
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"

Math

Appears 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}

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.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered 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"

Math	Appears 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}$

Comments

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. ~~~!

Samuraiwarm Tsunayoshi - 6 years, 5 months ago

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

Sharky Kesa - 6 years, 5 months ago

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

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.

Jubayer Nirjhor - 6 years, 5 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?

Mursalin Habib - 6 years, 5 months ago

Edited.

@Jubayer Nirjhor – $2^{q+1}+q^3\equiv 2\pmod 3$ ?

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

Siam Habib - 6 years, 5 months ago

@Siam Habib – 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$ .

@Samuraiwarm Tsunayoshi – 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$ .

@Siam Habib – Ow, just saw what you edited. Sorry!

@Siam Habib – Edited again. Is it OK now?

@Jubayer Nirjhor – Yes. It's OK!

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

Jake Lai - 6 years, 5 months ago

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

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

We're talking about juniors.

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.

Math	Appears 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}$