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,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 10100010^{1000} is a term in the sequence.

(b) Find the number of times the digit 55 occurs in the sum of all the terms in the sequence from 11 to 10100010^{1000}.

Q2

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

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

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

Q3

Find all positive integral values of aa, bb and cc such that

a+b=c2a + b = c^2

a2+b2=c3a^2 + b^2 = c^3

Q4

Find all primes pp and qq such that

pq+1+qp+1p^{q + 1} + q^{p + 1}

is a perfect square. Also state the perfect square.

Q5

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

Find the maximum number of elements in ABA \cup B.

Note by Sharky Kesa
4 years, 6 months ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   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 </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Q2

Let did_{i} be factors of nn such that 1=d1<di<dσ0(n)=n1 = d_{1} < d_{i} < d_{\sigma_{0}(n)} = n for all 1<i<σ0(n)1 < i < \sigma_{0}(n). (σ0(n)\sigma_{0}(n) is the number of divisors nn)

The function P(n)P(n) becomes

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

If nn is even, we get

P(n)=d1dσ0(n)×d2dσ0(n)1××dσ0(n)/2dσ0(n)/2+1=nσ0(n)2\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 nn is odd, we get

P(n)=d1dσ0(n)×d2dσ0(n)1××d(σ0(n)+1)/21d(σ0(n)+1)/2+1×(d(σ0(n)+1)/22)1/2=nσ0(n)12×n12=nσ0(n)2\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σ0(n)2P(n) = n^{\Large \frac{\sigma_{0}(n)}{2}}.

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

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

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

nσ0(n)2=225=32×52n^{\sigma_{0}(n)-2} = 225 = 3^{2}\times5^{2}.

Take log\log base nn on both sides we get

σ0(n)2=2×logn(15)\sigma_{0}(n)-2 = 2\times\log_{n}(15)

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

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

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

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

Samuraiwarm Tsunayoshi - 4 years, 6 months ago

Log in to reply

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

Sharky Kesa - 4 years, 6 months ago

Log in to reply

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

Samuraiwarm Tsunayoshi - 4 years, 6 months ago

Log in to reply

Prob 3: Squaring the first and dividing we get a2+2ab+b2a2+b2=1+2aba2+b2=c4c3=c\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 a2+b22ab    a2+b22aba^2+b^2\mid 2ab\implies a^2+b^2\le 2ab. By AM-GM we always have a2+b22aba^2+b^2\ge 2ab so we must have equality, that is a=ba=b. Thus c=2c=2 giving the only solution (a,b,c)=(2,2,2)(a,b,c)=(2,2,2).

Prob 4: If p,q>3p,q > 3 then pq+1qp+11(mod3)p^{q+1}\equiv q^{p+1}\equiv 1\pmod{3} since they are even powers of prime base. So their sum satisfies pq+1+qp+12(mod3)p^{q+1}+q^{p+1}\equiv 2\pmod 3 which is not a quadratic residue mod 33. So we must have at least one of p,q{2,3}p,q\in\{2,3\}. WLOG we let p{2,3}p\in\{2,3\}. If p=2p=2 and q>2q>2 then 2q+1+q3=t2    q3=(t+2(q+1)/2)(t2(q+1)/2)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=qit+2^{(q+1)/2}=q^i and t2(q+1)/2=qjt-2^{(q+1)/2}=q^j so 2(q+3)/2=qj(qij1)2^{(q+3)/2}=q^j\left(q^{i-j}-1\right) and then q=2q=2, a contradiction. On the other hand (p,q)=(2,2)(p,q)=(2,2) works with square 1616. If p=3p=3 then 3q+1+q4=t23^{q+1}+q^4=t^2 implies 3q+1=(t+q2)(tq2)3^{q+1}=\left(t+q^2\right)\left(t-q^2\right) so t+q2=3it+q^2=3^i and tq2=3jt-q^2=3^j giving 2q2=3j(3ij1)2q^2=3^j\left(3^{i-j}-1\right). Since qq is prime, we can easily observe that we must have j=2j=2 and i=3i=3 so that q=3q=3; or q=2q=2 and (i,j)=(2,0)(i,j)=(2,0). We check that none works.

Jubayer Nirjhor - 4 years, 6 months ago

Log in to reply

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

Mursalin Habib - 4 years, 6 months ago

Log in to reply

Edited.

Jubayer Nirjhor - 4 years, 6 months ago

Log in to reply

@Jubayer Nirjhor 2q+1+q32(mod3)2^{q+1}+q^3\equiv 2\pmod 3 ?

For q=5,2q+1+q30(mod3)q=5, 2^{q+1}+q^3\equiv 0\pmod 3.

Siam Habib - 4 years, 6 months ago

Log in to reply

@Siam Habib Yeah, this fact pq+1+qp+10(mod3)p^{q+1}+q^{p+1} \equiv 0 \pmod{3} only works for p,q>3p,q > 3. If you choose p=2p = 2, this fact doesn't always work for every prime qq.

Samuraiwarm Tsunayoshi - 4 years, 6 months ago

Log in to reply

@Samuraiwarm Tsunayoshi I didn't say that 2q+1+q30(mod3)2^{q+1} + q^3 \equiv 0 \pmod 3 for all primes qq. I just showed a counter example @Jubayer Nirjhor 's assumption that 2q=1+q32(mod3)2^{q=1} + q^3 \equiv 2 \pmod 3.

Siam Habib - 4 years, 6 months ago

Log in to reply

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

Samuraiwarm Tsunayoshi - 4 years, 6 months ago

Log in to reply

@Siam Habib Edited again. Is it OK now?

Jubayer Nirjhor - 4 years, 6 months ago

Log in to reply

@Jubayer Nirjhor Yes. It's OK!

Siam Habib - 4 years, 6 months ago

Log in to reply

Q1

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

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

an+1=2anan1=2(9n8)9(n1)+8a_{n+1} = 2a_{n}-a_{n-1} = 2(9n-8)-9(n-1)+8

=9(n+1)8= 9(n+1)-8

Since 101000(1+9)1000110008mod910^{1000} \equiv (1+9)^{1000} \equiv 1^{1000} \equiv -8 \mod 9 and our sequence contains all positive integers of the form 9n89n-8, 10100010^{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 - 4 years, 6 months ago

Log in to reply

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

Sharky Kesa - 4 years, 6 months ago

Log in to reply

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

Mursalin Habib - 4 years, 6 months ago

Log in to reply

We're talking about juniors.

Jubayer Nirjhor - 4 years, 6 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 - 4 years, 6 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...