Problem - 01 - National Math Camp 2021 Number Theory Exam - "GCD, Coprime, Divisibility"

Discussion on Bangladesh National Math Camp
User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:
Problem - 01 - National Math Camp 2021 Number Theory Exam - "GCD, Coprime, Divisibility"

Unread post by Anindya Biswas » Thu May 06, 2021 4:19 pm

Let $N$ be a nonzero integer. Given any $a,b$ such that $\text{gcd}(a,b,N)=1$. Prove that you can find $m,n$ such that $\text{gcd}(m,n)=1$ and $N|m-a, N|n-b$.
"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:

Re: Problem - 01 - National Math Camp 2021 Number Theory Exam - "GCD, Coprime, Divisibility"

Unread post by Anindya Biswas » Thu May 06, 2021 5:03 pm

Let $g=\text{gcd}(a,b)$
$\therefore\exists x,y\in\mathbb{Z}$ such that $\text{gcd}(x,y)=1$ and $a=gx, b=gy$.
By Bézout's identity, $\exists k_1,k_2\in\mathbb{Z}$ such that $k_2x-k_1y=1$.

Claim : Choosing $m=a+Nk_1,n=b+Nk_2$ satisfies the necessary condition.

Proof :
It's sufficient to prove that $\text{gcd}(m,n)=1$.
Assume for the sake of contradiction, there exists a prime number $p$ such that $p\mid m$ and $p\mid n$
$\therefore p\mid k_2m-k_1n$
$\Rightarrow p\mid g(k_2x-k_1y)$
$\Rightarrow p\mid g$
Since $\text{gcd}(a,b,N)=1$, $p\nmid N$.
$\therefore p\mid m-gx$ and $p\mid n-gy$
$\Rightarrow p\mid Nk_1$ and $p\mid Nk_2$
$\Rightarrow p\mid k_1$ and $p\mid k_2$
$\Rightarrow p\mid k_2x-k_1y$
$\Rightarrow p\mid 1$
Which is a contradiction. So, $m$ and $n$ has no common prime factor.
$\therefore \text{gcd}(m,n)=1$. $\text{Q.E.D.}$
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Nayer_Sharar
Posts:16
Joined:Mon Dec 21, 2020 9:26 pm

Re: Problem - 01 - National Math Camp 2021 Number Theory Exam - "GCD, Coprime, Divisibility"

Unread post by Nayer_Sharar » Wed Jun 16, 2021 8:09 pm

Let $ (a,N)=x , (b,N)=y$ then $ (x,y)=1$

By Dirichlet's theorem there exists infinitely many primes $p,q$ such that

$ p \equiv \dfrac{a}{x}$ (mod $\dfrac{N}{x}$) and $q \equiv \dfrac{b}{y}$ (mod $\dfrac {N}{y}$)

or, $px \equiv a $ (mod N) and $ qy \equiv b $ (mod N)

Setting $ m=px ,n = qy$ we are done

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

Re: Problem - 01 - National Math Camp 2021 Number Theory Exam - "GCD, Coprime, Divisibility"

Unread post by Anindya Biswas » Wed Jun 16, 2021 8:16 pm

Nayer_Sharar wrote:
Wed Jun 16, 2021 8:09 pm
Let $ (a,N)=x , (b,N)=y$ then $ (x,y)=1$

By Dirichlet's theorem there exists infinitely many primes $p,q$ such that

$ p \equiv \dfrac{a}{x}$ (mod $\dfrac{N}{x}$) and $q \equiv \dfrac{b}{y}$ (mod $\dfrac {N}{y}$)

or, $px \equiv a $ (mod N) and $ qy \equiv b $ (mod N)

Setting $ m=px ,n = qy$ we are done
People who used such heavy theorem on such easy/trivial problem got less marks as a penalty.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Nayer_Sharar
Posts:16
Joined:Mon Dec 21, 2020 9:26 pm

Re: Problem - 01 - National Math Camp 2021 Number Theory Exam - "GCD, Coprime, Divisibility"

Unread post by Nayer_Sharar » Wed Jun 16, 2021 10:38 pm

Anindya Biswas wrote:
Wed Jun 16, 2021 8:16 pm
Nayer_Sharar wrote:
Wed Jun 16, 2021 8:09 pm
Let $ (a,N)=x , (b,N)=y$ then $ (x,y)=1$

By Dirichlet's theorem there exists infinitely many primes $p,q$ such that

$ p \equiv \dfrac{a}{x}$ (mod $\dfrac{N}{x}$) and $q \equiv \dfrac{b}{y}$ (mod $\dfrac {N}{y}$)

or, $px \equiv a $ (mod N) and $ qy \equiv b $ (mod N)

Setting $ m=px ,n = qy$ we are done
People who used such heavy theorem on such easy/trivial problem got less marks as a penalty.
Well its better to get 4-5 instead of 0 and another thing is i solved it with lighter materials.I just wanted to post a different solution. This is what the forum is all about, sharing different ideas. :(

otis
Posts:17
Joined:Wed Aug 24, 2022 10:03 am

Re: Problem - 01 - National Math Camp 2021 Number Theory Exam - "GCD, Coprime, Divisibility"

Unread post by otis » Wed Aug 24, 2022 10:08 am

Suppose an integer N is given. Prove that there exists an integer N* such that |N|>K and |N*|K.
If K is a positive integer, then the implication holds as well. among us
If K=1, then given any positive integer b, there exists a positive integer N such that |b|>N and |N|b .
This result also applies to negative integers. For example, if K=−1, then given any negative odd integer c, there exists a negative even integer N such that |c|>N and |c|c . framed game
Similarly, if K=3, then given any positive odd integer a, there exists a positive even integer N such a + 1 > a + 2 > a − 2 > a − 1 > N − a > = 0 , where N is the largest odd prime number less than or equal to a .
Similarly, if K=5, then there exist integers b1 , b2 , ... such that b1 + b2 +…> K − 1 > b1 + b2 + …> b1 − b2 − …> ≤ 1 (for all i ∈ [ b1 , b2 , ...] ) .
Similarly b1 + b2 +…> ≤ K for all

Post Reply