Number Theory is my bias wrecker

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

Solution: We know that 

$$(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 💜