Waste less time on Facebook — follow Brilliant.
×

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.

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
2 years, 11 months ago

No vote yet
1 vote

  Easy Math Editor

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 \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

Sort by:

Top Newest

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

Samuraiwarm Tsunayoshi - 2 years, 11 months ago

Log in to reply

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

Sharky Kesa - 2 years, 11 months ago

Log in to reply

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

Samuraiwarm Tsunayoshi - 2 years, 11 months ago

Log in to reply

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 - 2 years, 11 months ago

Log in to reply

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 - 2 years, 11 months ago

Log in to reply

Edited.

Jubayer Nirjhor - 2 years, 11 months ago

Log in to reply

@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 - 2 years, 11 months ago

Log in to reply

@Siam Habib Edited again. Is it OK now?

Jubayer Nirjhor - 2 years, 11 months ago

Log in to reply

@Jubayer Nirjhor Yes. It's OK!

Siam Habib - 2 years, 11 months ago

Log in to reply

@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 - 2 years, 11 months ago

Log in to reply

@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 - 2 years, 11 months ago

Log in to reply

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

Samuraiwarm Tsunayoshi - 2 years, 11 months ago

Log in to reply

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

Mursalin Habib - 2 years, 11 months ago

Log in to reply

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.

Sharky Kesa - 2 years, 11 months ago

Log in to reply

We're talking about juniors.

Jubayer Nirjhor - 2 years, 11 months ago

Log in to reply

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.

Jake Lai - 2 years, 11 months ago

Log in to reply

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

Sharky Kesa - 2 years, 11 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...