Some GCD Problems

For discussing Olympiad Level Number Theory problems
tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh
Some GCD Problems

Unread post by tanmoy » Sat Feb 28, 2015 6:44 pm

(1) Show that if $a$and $b$ are relatively prime integers, then $gcd(a+b,a^{2}-ab+b^{2}) = 1$ or $3$.
(2) Show that if $a$ and $b$ are relatively prime integers, and $p$ is an odd prime, then $gcd(a+b,\frac{a^{p}+b^{p}} {a+b})=1$ or $p$.
(3)Show that if $a,m,n$ are positive with $m\neq n$,then $gcd(a^{2^{m}}+1,a^{2^{n}}+1)=1$ if $a$ is even and $2$ if $a$ is odd.
"Questions we can't answer are far better than answers we can't question"

Tahmid
Posts:110
Joined:Wed Mar 20, 2013 10:50 pm

Re: Some GCD Problems

Unread post by Tahmid » Sun Mar 01, 2015 3:41 pm

just apply $euclidean$ $algorithm$. nothing else.

tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh

Re: Some GCD Problems

Unread post by tanmoy » Sun Mar 01, 2015 8:02 pm

Tahmid wrote:just apply $euclidean$ $algorithm$. nothing else.
I have solved $1$ and $2$ using $\text{Euclidean Algorithm}$.
$\text{Solution of 3}:$
WLOG,assume that $m>n$.$a^{2^{n}}+1$ is a divisor of $a^{2^{m}}-1$.$\therefore gcd(a^{2^{m}}-1+2,a^{2^{n}}+1)=1$ if $a$ is even and $2$ if $a$ is odd.
"Questions we can't answer are far better than answers we can't question"

Tahmid
Posts:110
Joined:Wed Mar 20, 2013 10:50 pm

Re: Some GCD Problems

Unread post by Tahmid » Mon Mar 02, 2015 12:44 am

tanmoy wrote:.$a^{2^{n}}+1$ is a divisor of $a^{2^{m}}-1$.
how ? :?: :?:
$a=3$ ; $n=2$ ; $m=3$ breaks it .

Nirjhor
Posts:136
Joined:Thu Aug 29, 2013 11:21 pm
Location:Varies.

Re: Some GCD Problems

Unread post by Nirjhor » Mon Mar 02, 2015 3:47 am

Tahmid wrote:
tanmoy wrote:.$a^{2^{n}}+1$ is a divisor of $a^{2^{m}}-1$.
how ? :?: :?:
$a=3$ ; $n=2$ ; $m=3$ breaks it .
I can't see $(a,n,m)=(3,2,3)$ yielding a contradiction.

In fact, if $A_n=a^{2^n}+1$ and $A_m=a^{2^m}-1$ and $m=n+j$ then \[a^{2^n}\equiv -1~\left(\bmod ~A_n\right)\Longrightarrow \left(a^{2^n}\right)^{2^j}\equiv (-1)^{2^j}\Longrightarrow a^{2^{n+j}}\equiv 1\Longrightarrow A_m\equiv 0~\left(\bmod~A_n\right).\]
- What is the value of the contour integral around Western Europe?

- Zero.

- Why?

- Because all the poles are in Eastern Europe.


Revive the IMO marathon.

tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh

Re: Some GCD Problems

Unread post by tanmoy » Mon Mar 02, 2015 11:48 am

Tahmid wrote:
tanmoy wrote:.$a^{2^{n}}+1$ is a divisor of $a^{2^{m}}-1$.
how ? :?: :?:
$a=3$ ; $n=2$ ; $m=3$ breaks it .
$3^{2^{2}}+1=3^{4}+1=82$ and $3^{2^{3}}-1=3^{8}-1=6560.6560\div 82=80$.
"Questions we can't answer are far better than answers we can't question"

Tahmid
Posts:110
Joined:Wed Mar 20, 2013 10:50 pm

Re: Some GCD Problems

Unread post by Tahmid » Mon Mar 02, 2015 12:02 pm

i thought $a^{2^{n}}=(a^{2})^{n}$ but you meant $a^{2^{n}}=a^{(2^{n})}$
sorry for the mistake . :oops:

Post Reply