It's a hard knock life

If gcd ( a , b ) = 1 \gcd(a, b) = 1 , p p is a prime, a + b a + b is not a multiple of p p , then what is:

gcd ( a p + b p a + b , a + b ) ? \gcd\left(\frac{a^p + b^p}{a + b}, a + b\right)?

Assume that a a , b b and p p are positive integers.


The answer is 1.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

if n n is an odd number then

a n + b n = ( a + b ) ( i = 0 n 1 a i b n 1 i ( 1 ) i ) a^n+b^n=(a+b)(\sum_{i=0}^{n-1}a^ib^{n-1-i}(-1)^i)

so

a p + b p = ( a + b ) ( i = 0 n 1 a i b p 1 i ( 1 ) i ) a n + b n a + b = i = 0 n 1 a i b p 1 i ( 1 ) i a^p+b^p=(a+b)(\sum_{i=0}^{n-1}a^ib^{p-1-i}(-1)^i) \implies \frac{a^n+b^n}{a+b}=\sum_{i=0}^{n-1}a^ib^{p-1-i}(-1)^i

by repeatedly applying Euclidean algorithm, we find the GCD to be

G C D ( i = 0 n 1 a i b p 1 i ( 1 ) i , a + b ) = G C D ( p b p 1 , a + b ) = 1 GCD(\sum_{i=0}^{n-1}a^ib^{p-1-i}(-1)^i,a+b)=GCD(pb^{p-1},a+b)=1

since ( a + b , p ) = 1 (a+b,p)=1 and ( a + b , b t ) = 1 t N (a+b,b^t)=1 \ \forall t\in \mathbb{N}

Edit:

As requested by Sonu Gupra, I decided to make the proof more accurate, for the case p = 2 p=2 .

The GCD would be defined if a 2 + b 2 a + b \frac{a^2+b^2}{a+b} is a whole number. So, we check the condition, for which is a whole number.

a + b a 2 + b 2 = ( a + b ) 2 2 a b a + b 2 a b a+b | a^2+b^2=(a+b)^2-2ab \implies a+b | 2ab

as g c d ( a , b ) = 1 gcd(a,b)=1 , this is only possible if a + b = 2 a+b=2 . because, if q 2 a b q | 2ab , for a prime q a + b , q > 2 q | a+b \ , \ q>2 , then either q a q|a or q b q|b . this is contradiction, since if q a q|a and g c d ( a , b ) = 1 gcd(a,b)=1 then q a + b q \nmid a+b . Therefore, a + b a+b can only be 2 2 , meaning a = 1 , b = 1 a=1,b=1 . Consequently, one realises that the final answer stays the same.

one more condition if n=2 then nothing say in solution.

sonu gupra - 2 years, 6 months ago

Log in to reply

thanks for pointing out the deficiency. I have added an extension to explain more, although I usually don't write accurate proofs. Rigorous proofs are boring!

A Former Brilliant Member - 2 years, 6 months ago

in this a^p+b^p/(a+b) may be not inteser

sonu gupra - 2 years, 6 months ago

Log in to reply

if it is not an integer, then the main question would not make sense either, since the GCD is defined only for integers.

A Former Brilliant Member - 2 years, 6 months ago
Jeremy Galvagni
Nov 25, 2018

Logically, if the answer is a single number then that number must be 1.

If it were anything else it would have to be some expression in terms of a a and b b .

that's why 47 people have submitted the right answer :D But I still don't get how they rank the questions...

A Former Brilliant Member - 2 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...