NT marathon!!!!!!!

For discussing Olympiad Level Number Theory problems
User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh
Problem:11

Unread post by Mehrab4226 » Mon Mar 29, 2021 10:33 am

Problem:11
Show that for all positive integers $n$, $81$ divides $10^{n+1}-9n-10$
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Problem:11

Unread post by Anindya Biswas » Mon Mar 29, 2021 11:32 am

Mehrab4226 wrote:
Mon Mar 29, 2021 10:33 am
Problem:11
Show that for all positive integers $n$, $81$ divides $10^{n+1}-9n-10$
Let $a_n=10^{n+1}-9n-10$
Here, $a_1=81$, so $81|a_1$, which is our base case for induction.
Induction Hypothesis : Let's assume $81|a_n$
Inductive step :
Observe that $a_{n+1}-a_n=9(10^{n+1}-1)$
Since $9|10^{n+1}-1$,
We can easily see that $81|a_{n+1}-a_n\Rightarrow 81|a_{n+1}$
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: Problem 12

Unread post by Asif Hossain » Fri Apr 02, 2021 10:34 am

SInce no body posting probs that's why here is one
Find all $n,a \in \mathbb{N}$ Such That $n!+25=a^2$
Source: a brother of mine
Hmm..Hammer...Treat everything as nail

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: Problem 12

Unread post by Asif Hossain » Fri Apr 02, 2021 11:54 am

Asif Hossain wrote:
Fri Apr 02, 2021 10:34 am
SInce no body posting probs that's why here is one
Find all $n,a \in \mathbb{N}$ Such That $n!+25=a^2$
Source: a brother of mine
Solution (maybe idk :? )
We claim $(n,a)=(4,7)$ is the only solution

Let $n \geq 5$ then since $5|n!$ so $5|a^2$ or $5|a$
Let $a:=5k$ so we can rewrite the equation as $n!+25=25k^2$ then it implies $n \geq 10$ and it is also easy to see $k$ must be odd.
After some calculation $n(n-1)...11.9....6.4.3.4.1=(k+1)(k-1)$
let $k=2k'+1$ then we get $n(n-1)...(6.4.3.1)=k'(k'+1)$ notice $k'$ and $k'+1$ are consecutive integer .

Now we run induction that the expression can't be written as product of $2$
Base case is $11.9.8.7.6.4.3.1$ it can be easily shown that can't be wrote as product of $2$ consecutive integers.
let $11.9.8.7.6.4.3.1=l$ we assume $n(n-1)...l=f$ can't be wrote as $2$ consecutive integers product
Let $m$ and $t$ be such divisors of ST $mt=f$ and $(n+1)mt=k'(k'+1)$
we know that $m$ and $n$ are not consecutive

Now WLOG assume $(n+1)m=t+1 \Rightarrow (n+1)f=t(t+1)$
$t+1$ doesn't divide $f$ so $t+1|n+1$
but $n+1|t+1$ so $(n+1)=t+1 \Rightarrow n=t$
.Contradiction and we are done
Hmm..Hammer...Treat everything as nail

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Problem:13

Unread post by Mehrab4226 » Wed Apr 07, 2021 10:08 am

For a positive integer $p$, define the positive integer $n$ to be $p$-safe if $n$ differs in absolute value by more than $2$ from all multiples of $p$. For example, the set of $10$-safe numbers is $\{ 3, 4, 5, 6, 7, 13, 14, 15, 16, 17, 23, \ldots\}$. Find the number of positive integers less than or equal to $10,000$ which are simultaneously $7$-safe, $11$-safe, and $13$-safe.
Source:
AIME:2012
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Solution to problem:13

Unread post by Anindya Biswas » Wed Apr 07, 2021 9:12 pm

Mehrab4226 wrote:
Wed Apr 07, 2021 10:08 am
For a positive integer $p$, define the positive integer $n$ to be $p$-safe if $n$ differs in absolute value by more than $2$ from all multiples of $p$. For example, the set of $10$-safe numbers is $\{ 3, 4, 5, 6, 7, 13, 14, 15, 16, 17, 23, \ldots\}$. Find the number of positive integers less than or equal to $10,000$ which are simultaneously $7$-safe, $11$-safe, and $13$-safe.
Source:
AIME:2012
A number $x$ will be $7$ safe if $x\equiv3,4\pmod{7}$
A number $x$ will be $11$ safe if $x\equiv3,4,5,6,7,8\pmod{11}$
A number $x$ will be $13$ safe if $x\equiv3,4,5,6,7,8,9,10\pmod{13}$
By Chinese Remainder Theorem, since $7,11,13$ are pairwise coprime integers, this system of linear congruences has unique solution in $\pmod {1001}$.
There are $2\times6\times8=96$ systems of congruences and each corresponds to a residue class for which a number will be simultaneously $7,11,13$-safe.
So, there are $96$ numbers less than or equal to $1001$ which are simultaneously $7,11,13$-safe.
So, there are $96\times10=960$ numbers less than or equal to $1001\times10=10010$ which are simultaneously $7,11,13$-safe.
And there are $2$ numbers that are between $10000$ and $10010$ which are simultaneously $7,11,13$-safe.
So, the final answer is $\boxed{960-2=958}$.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Problem 14

Unread post by Anindya Biswas » Thu Apr 08, 2021 10:23 am

Let $a_1,a_2,a_3,\dots$ be a sequence of positive integers such that $\text{gcd}(a_m,a_n)=\text{gcd}(m,n)$ where $m\neq n$ and $m,n$ positive integers. Prove that $a_m=m$ for all positive integer $m$.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

~Aurn0b~
Posts:46
Joined:Thu Dec 03, 2020 8:30 pm

Re: Problem 14

Unread post by ~Aurn0b~ » Thu Apr 08, 2021 2:39 pm

Anindya Biswas wrote:
Thu Apr 08, 2021 10:23 am
Let $a_1,a_2,a_3,\dots$ be a sequence of positive integers such that $\text{gcd}(a_m,a_n)=\text{gcd}(m,n)$ where $m\neq n$ and $m,n$ positive integers. Prove that $a_m=m$ for all positive integer $m$.
$\textbf{Solution 14}$
$gcd(a_{2m},a_m)=gcd(2m,m)=m\ \ \Rightarrow\ \ m\mid a_m$

Assume that $m\neq k$. Let $a_m=k$. Then, $$k=gcd(a_k,k)=gcd(a_k,a_m)=gcd(k,m)$$

$$\Rightarrow k=gcd(k,m)$$

$\Rightarrow k\mid m \Rightarrow a_m\mid m$
We also know that $m\mid a_m$. Therefore, $a_m=m$. Contradiction as we've assumed that $m\neq k$. So $a_m=m.\blacksquare$
Last edited by ~Aurn0b~ on Thu Apr 08, 2021 2:56 pm, edited 1 time in total.

~Aurn0b~
Posts:46
Joined:Thu Dec 03, 2020 8:30 pm

Re: NT marathon!!!!!!!

Unread post by ~Aurn0b~ » Thu Apr 08, 2021 2:47 pm

$\textbf{Problem 15}$

Let $\mathbb{P}$ be the set of all prime numbers. Find all functions $f:\mathbb{P}\rightarrow\mathbb{P}$ such that:
\[ f(p)^{f(q)}+q^p=f(q)^{f(p)}+p^q \] Holds for all $p,q\in\mathbb{P}$.

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: NT marathon!!!!!!!

Unread post by Mehrab4226 » Fri Apr 09, 2021 3:05 pm

~Aurn0b~ wrote:
Thu Apr 08, 2021 2:47 pm
$\textbf{Problem 15}$

Let $\mathbb{P}$ be the set of all prime numbers. Find all functions $f:\mathbb{P}\rightarrow\mathbb{P}$ such that:
\[ f(p)^{f(q)}+q^p=f(q)^{f(p)}+p^q \] Holds for all $p,q\in\mathbb{P}$.
We claim: $f(p)=p$ is the only function. We will try to prove it by induction.
Let,
$p(p,q)=f(p)^{f(q)}+q^p=f(q)^{f(p)}+p^q$
Now,
$p(2,p)$ for some prime p we get,
$f(2)^{f(p)}+p^2=f(p)^{f(2)}+2^p=x$
X can be both be odd or even,
  • Case:1 if X is odd then,
    $f(2)^f(p)$ is even, which implies, $f(2)=2$
  • Case:2 if X is even then,
    $f(p)^f(2) $ is even, which implies $f(p)=2$, for all p
    But if we take, $p(p,q)$ we can find a contradiction which is ,
    $p^q=q^p$ which is obviously not true, as p and q are primes.
$\therefore f(2)=2$,
base case done.

Let us assume that for some prime $p_k$ the function holds,
and $p_{k+1}$ be the smallest prime number greater than $p_k$

$p(p_k,p_{k+1})=f(p_k)^{f(p_{k+1})}+p_{k+1}^{p_k}=f(p_{k+1})^{p_k}+p_{k}^{p_{k+1}}$
$=p_k^g+p_{k+1}^{p_k}=g^{p_k}+p_k^{p_{k+1}}$[let $f(p_{k+1})=g$]
Or,$p_k^g-p_k^{p_{k+1}}=g^{p_k}-p_{k+1}^{p_k}$
L.H.S is divisible by p, so,
$g^{p_k} \equiv p_{k+1}^{p_k} (\text{mod }p_k)$
Or,$\frac{g^{p_k}}{p_{k+1}^{p_k}} \equiv (\frac{g}{p_{k+1}})^{p_k} \equiv1 (\text{mod }p_k)$ as $GCD(p_k,p_{k+1})=1$
Now this holds iff $\frac{g}{p_{k+1}}$ is an integer,

$\therefore p_{k+1}|g$
but $g$ and $p_{k+1}$ are prmes
$\therefore g= f(p_{k+1})=p_{k+1}$
Which was our inductive step,
$\therefore f(p)=p$ $ \forall p \in \mathbb{P}$
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Post Reply