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

No vote yet
1 vote

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

Log in to reply

@Samuraiwarm Tsunayoshi You know there is a much easier solution in terms of appearance. Sharky Kesa · 2 years, 3 months ago

Log in to reply

@Sharky Kesa What I did is proving the general formula. =w= Samuraiwarm Tsunayoshi · 2 years, 3 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, 3 months ago

Log in to reply

@Jubayer Nirjhor 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, 3 months ago

Log in to reply

@Mursalin Habib Edited. Jubayer Nirjhor · 2 years, 3 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, 3 months ago

Log in to reply

@Siam Habib Edited again. Is it OK now? Jubayer Nirjhor · 2 years, 3 months ago

Log in to reply

@Jubayer Nirjhor Yes. It's OK! Siam Habib · 2 years, 3 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, 3 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, 3 months ago

Log in to reply

@Siam Habib Ow, just saw what you edited. Sorry! Samuraiwarm Tsunayoshi · 2 years, 3 months ago

Log in to reply

Isn't 4 hours a little too generous for this set? Mursalin Habib · 2 years, 3 months ago

Log in to reply

@Mursalin Habib 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, 3 months ago

Log in to reply

@Mursalin Habib We're talking about juniors. Jubayer Nirjhor · 2 years, 3 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, 3 months ago

Log in to reply

@Jake Lai I'll tell you that it's very easy to do with arithmetic sum formula. Sharky Kesa · 2 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...