0
$\begingroup$

So you have two numbers $a$ and $b$ coprime. You then consider $\frac{a^{37} + b^{37}}{a + b}$ and $a + b$. When do these two values share common factors, and what are these common factors?

My Work

So the first term can be written as $\sum_{n=0}^{36}(-1)^{n}a^{n}b^{36-n} = a^{36}-a^{35}b^{1}+a^{34}b^{2}-\dots-ab^{35}+b^{36}$. The second term is still $a+b$. I've run this through a script on my HP-50g, and found that these two terms appear to be relatively prime iff 37 does not divide $a+b$. Conversely, if 37 divides $a+b$, then 11 is the only common prime factor of the two terms, and so gcd$\left(\frac{a^{37} + b^{37}}{a + b}, a+b\right)$ = 37.

Is there any way to prove this?

$\endgroup$
1
1
$\begingroup$

Note: $b\equiv -a\pmod {a+b}$ and:

$$\begin{align}\frac{a^{37}+b^{37}}{a+b}&=\sum_{n=0}^{36} (-1)^na^nb^{36-n} \\&\equiv \sum_{n=0}^{36}(-1)^n(-1)^{36-n}a^{36}\pmod{a+b}\\ &=a^{36}(1+1+\cdots +1)\\&=37a^{36}\pmod{a+b} \end{align}$$

Since $\gcd(a+b,a)=1$ you can conclude what?

More generally, if $u,v$ are distinct relatively prime integers and $d>0$ then:

$$\gcd\left(\frac{u^d-v^d}{u-v},u-v\right)=\gcd(d,u-v)$$

Here $u=a,v=-b,d=37$.

We are using three results here:

Theorem: If $m\equiv n\pmod d$ then $\gcd(m,d)=\gcd(n,d).$

Theorem: If $\gcd(m,n)=1$ then $\gcd(dm,n)=\gcd(d,n).$

Theorem: If $\gcd(m,n)=1$ then $\gcd(m^d,n)=1.$

$\endgroup$
0
$\begingroup$

Assume that $a+b = 0 \mod 37$, meaning $a+b= 37 k$ for $k \in \mathbb{N}$.

So we have $GCD(\frac{a^{37}+b^{37}}{a+b} , 37k)$

$a=37 k-b$, so we have $\frac{(37k-b)^{37}+b^{37}}{37 k} = \frac{b^{37}+\sum \limits_{j=0}^{37} \binom{37}{j} (37 k)^j (-b)^{37-j} }{37k}$

its obvious that when $j>1$ we have $37^2$ as multiple of some number.

and when $j=0$ we have $(-b)^{37} = -b^{37}$ and $-b^{37}+b^{37} =0$.

So we have $\frac{b^{37}+\sum \limits_{j=0}^{37} \binom{37}{j} (37 k)^j (-b)^{37-j} = 37^2 k m}{37 k} = 37 m$ for $m \in \mathbb{N}$.

Thus $GCD(\frac{a^37+b^37}{a+b},a+b) = 37$ if $a+b = 0 \mod 37$.

$\endgroup$
0
$\begingroup$

Use $$a\equiv -b\mod (a+b)$$ to derive $$\frac{a^{37}+b^{37}}{a+b}\equiv 37b^{36}\mod (a+b)$$

This means that every number $p$ dividing both $\frac{a^{37}+b^{37}}{a+b}$ and $a+b$ also divides $37b^{36}$. If some prime factor of $p$ would divide $b$, it would also divide $a$, contradicting the assumption $\gcd(a,b)=1$. Hence, $p$ must divide $37$, so you get $p=37$ as the only non-trivial possibility. So, the only non-trivial common factor is $37$. And we have this common factor if and only if $a+b$ is divisble by $37$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.