Welcome Back to mah blog!
I thought I should revise Number theory and solve problems of IOQM level!
Also, NT is definitely my bias wrecker ( Kpop term used to describe the second favourite which has huge chances to become your favourite!)
Problem 1 (2019 AMC 12A): For some positive integer $k$, the repeating base-$k$ representation of the (base-ten) fraction $\frac{7}{51}$ is $0.23_k = 0.232323\dots_k .$ What is $k$?
Solution: Note that $$ 0.232323\dots_k= \frac{ 2}{k}+\frac{3}{k^2}+\frac{2}{k^2}+\frac{3}{k^4}\dots$$
$$= \frac{2}{k}+\frac{2}{k^3}+\dots + \frac{3}{k^2}+\frac{3}{k^4}+\dots $$
$$ = \frac{2/k+3/k^2}{1-\frac{1}{k^2}}=\frac{7}{51}\implies k= 16.$$
Problem 2[ AIME 2008 II]: There exist $r$ unique nonnegative integers $n_1 > n_2 > \cdots > n_r$ and $r$ integers $a_k$ ($1\le k\le r$) with each $a_k$ either $1$ or $- 1$ such that $$a_13^{n_1} + a_23^{n_2} + \cdots + a_r3^{n_r} = 2008.$$ Find $n_1 + n_2 + \cdots + n_r$.
Solution: Note that $$\overline{2008}_{10} = \overline{2202101}_{3}.$$ And replacing $$2\cdot 3^k=3^{k+1}-3^k.$$ We get $$2008= 1+3^2-3^3+3^4-3^5+3^6-3^6+3^7=1+3^2-3^3+3^4-3^5+3^7$$
So, we get $\boxed{21}$ as the answer.
Problem 3: Determine the smallest positive integer $n$ which satisfies the congruence
$$n + n^{-1}\equiv 25 \pmod 143.$$
Solution: Note that, $$ \frac{1}{n}+n\equiv 25 \pmod 143 $$
$$ \implies n^2+1-25n\equiv 0\pmod 143$$
$$ \implies n^2+144-25n \equiv 0\pmod 143$$
$$\implies n^2-25n+144=(n-16)(n-9)\pmod 143$$
So $n\le 9,$ also $n<9$ doesn't work. So $n=\boxed{9}.$
Problem 4: Show that there are no integers $a, b, c$ for which $a^2 + b^2 - 8c = 6.$
Proof: Take $mod 8.$
Problem 5: Show that $a^{p(p-1)}\equiv 1 \mod p^2$
Proof: It's true by euler's theorem, so let's not use that.
We proceed the same way, we prove euler's theorem :P
$$a\cdot 2a \cdot 3a\dots, p-1\cdot a \cdot p+1\cdot a \dots (p^2-1) \cdot a \equiv 1\cdot 2\cdot \dots (p^2-1)\mod p^2$$
$$\implies a^{p(p-1}\equiv 1\mod p^2$$
Another way is to use the fact that $$a^{p-1}\equiv 1\mod p\implies a^{p-1}\equiv 1, p+1, 2p+1,\dots p(p-1)+1\mod p^2$$
So $$a^{p(p-1)}\equiv 1^p, (p+1)^p,\dots , (p(p-1))^p \mod p^2$$
So $$a^{p(p-1)}\equiv 1\mod p^2$$
Problem 6 [ Math prize 2009]: When the integer $ {\left(\sqrt{3} + 5\right)}^{103} - {\left(\sqrt{3} - 5\right)}^{103}$ is divided by 9, what is the remainder?
Solution: Note that $$ {\left(\sqrt{3} + 5\right)}^{103} - {\left(\sqrt{3} - 5\right)}^{103}={\left(\sqrt{3} + 5\right)}^{103}+{\left(5-\sqrt{3} \right)}^{103}$$
$$=2\left( 5^{103}+\binom{103}{2}5^{101}\cdot 3+\dots +3^{51}\right)\equiv 2\left( 5^{103}+\binom{103}{2}5^{101}\cdot 3 \right)\equiv \boxed{1}\mod 9. $$
Problem 7[ 2016 CMIMC]: Determine the smallest positive prime $p$ which satisfies the congruence
$$p+ p^{-1}\equiv 25 \pmod 143.$$
$$(p-9)(p-16)\equiv 0\mod 11\cdot 13$$
Then by CRT $$(p-9)(p-16)\equiv 0\mod 11\implies 9, 5\mod 11$$
$$(p-9)(p-16)\equiv 0\mod 13\implies 9,3 \mod 13$$
So the solutions are $$9, 16, 42, 126 \mod 143.$$ The smallest is $\boxed{269}.$
Problem 8: Find all primes $p$ such that $p$ divides $2^p + 1.$
Solution: Note that $2^p+1\equiv 3\mod p\implies p=3$
Problem 9[ Wilson theorem]: Prove that if $p$ is a prime then $(p - 1)! \equiv -1 \pmod p.$
Proof: It's pretty well known, but I will write for myself. We use the fact that only $1,p-1$ are self inverses of itself. Rest all the numbers have a unique and distinct inverse, forming pair whose product is $1\mod p.$ So
$$2\cdot 3\cdot 4\dots p-2\equiv 1\mod p\implies 1\cdot 2\cdot 3\cdot 4\dots p-1\equiv p-1\mod p $$
Problem 10[ 1989 IMO P5]: Prove that for each positive integer $ n$ there exist $ n$ consecutive positive integers none of which is an integral power of a prime number.
Proof: We consider $k!+2, k!+3,\dots k!+n+1$ and take $k>>>>>n.$ Then
For any $2\le a\le n+1,$ $k!+a=a(k!/a+1)$ but $a|k!/a\implies $ two distinct prime factors divide $k!+a.$
Problem 11[Simpler CMIMC 2016]: Define a tasty residue of $n$ to be an integer
$1 \le a \le n$ such that there exists an integer $m > 1$ satisfying $a^m \equiv a (mod n). Find
the number of tasty residues of prime $p.$
Solution: It's $\phi{p}+1$ as $$a^{m}-a\equiv 0\mod p\implies p|a , p|a^{m-1}-1$$
Problem 12[CMIMC 2016]: Define a tasty residue of $n$ to be an integer
$1 \le a \le n$ such that there exists an integer $m > 1$ satisfying $a^m \equiv a (mod n). Find
the number of tasty residues of prime $2016.$
Solution: $2016= 2^5\cdot 3^2 \cdot 7$
We know that for any prime $p$ dividing $a^m-a$ we get $\phi{p}+1$ values of $a$ satisfying.
By CRT, we get $(\phi{2^5}+1)(\phi{3^2}+1)(\phi{7}+1)=\boxed{833}$ values.
Problem 13[ 2019 AIME P1]: Find the least odd prime factor of $2019^8 + 1.$
Solution: Since $$p|2019^8+1\implies p|2019^{16}-1\implies \phi{p}|16 \implies ord_p(2019)=16|\phi{p-1}$$
Clearly, $p=17$ doesn't work, and $p=97$ work.
Problem 14[USAMO]:Suppose that the set $\{1, 2, \dots , 1998\}$ has been parti-
tioned into disjoint pairs $\{a_i , b_i \} (1 ≤\le i \le 999)$ so that for all $i$, $|a_i - b_i |$ equals $1$ or $6.$
Prove that the sum
$$|a_1 - b_1 | + |a_2 - b_2 | + \dots + |a_{999} − b_{999} |$$
ends in the digit $9$.
Proof: Note we just have to show that the answer is $-1 \pmod {10}$. We will show that
the answer is $1 \pmod 2 , 4 \pmod 5$ .
Note that $a_i - b_i$ and $a_i + b_i$ have the same parity.
So the sum is $1+2+\dots +1998 \pmod 2 \equiv 1 \pmod 2 .$
And $|a_i - b_i |$ is always $1 \pmod 5$ . Hence the sum is $1\cdot 999\equiv 4\pmod 5 $ .
By CRT we are done.
So yeee! Hope you have a nice day!
Sunaina 💜
Thanks a lot for posting ioqm level problems!
ReplyDeleteWelcome!!! All the best for ioqm!
DeleteNice!
ReplyDeleteAlso try All Russian MO 2014 G9 P1,All Russsian MO 2015 G11P?(Forgot the problem number but pretty sure that the year is correct),2018 ARO G10 P4
For more beautiful NT probs
hey! Thanks for commenting! I will try those! Actually I have an upcoming post, where I am going to share ARMO problems! So really thankyou!
Delete