Problem - 01 - National Math Camp 2021 Number Theory Exam - "GCD, Coprime, Divisibility"
- Anindya Biswas
- Posts:264
- Joined:Fri Oct 02, 2020 8:51 pm
- Location:Magura, Bangladesh
- Contact:
![](./images/icons/misc/star.gif)
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
— John von Neumann
- 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"
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.}$
$\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
— John von Neumann
-
- Posts:16
- Joined:Mon Dec 21, 2020 9:26 pm
Re: Problem - 01 - National Math Camp 2021 Number Theory Exam - "GCD, Coprime, Divisibility"
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
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
- 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"
People who used such heavy theorem on such easy/trivial problem got less marks as a penalty.Nayer_Sharar wrote: ↑Wed Jun 16, 2021 8:09 pmLet $ (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
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
— John von Neumann
— John von Neumann
-
- Posts:16
- Joined:Mon Dec 21, 2020 9:26 pm
Re: Problem - 01 - National Math Camp 2021 Number Theory Exam - "GCD, Coprime, Divisibility"
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.Anindya Biswas wrote: ↑Wed Jun 16, 2021 8:16 pmPeople who used such heavy theorem on such easy/trivial problem got less marks as a penalty.Nayer_Sharar wrote: ↑Wed Jun 16, 2021 8:09 pmLet $ (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
![Sad :(](./images/smilies/icon_e_sad.gif)
Re: Problem - 01 - National Math Camp 2021 Number Theory Exam - "GCD, Coprime, Divisibility"
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
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