Math Genius: Rational approximations with denominators restricted to certain residue classes

Original Source Link

In certain contexts in Diophantine approximation, it is important for the denominators of the convergents to be restricted to a certain residue class. Consider, for instance, this problem where it is shown that $sum_{n geq 1} sin^{n}(n)$ diverges. In their solutions, the answerers utilized the fact that $pi/2$ has infinitely many convergents $p/q$ with odd denominators.

This question concerns whether, in the general case, restricting the denominators to certain residue classes makes no “significant” difference to the theory.

The specific questions I’d ask are as follows. Recall that to each irrational $alpha$, there are two standard quantities we associate to $alpha$ which measure its approximability.

One is the irrationality measure $lambda(alpha) = supleft{mu >0 : |alpha – p/q|<frac{1}{q^{mu}} text{has infinitely many} text{solutions} p,q in mathbb{Z}, q neq 0right}$. The other is the so-called Markov constant $M(alpha) = supleft{C>0: |alpha – p/q|<frac{1}{Cq^{2}} text{has infinitely many} text{solutions} p,q in mathbb{Z}, q neq 0right}$.

Now, let $a,b in mathbb{N}$, and define $lambda_{a,b}(alpha), M_{a,b}(alpha)$ similar to above, but with the additional constraint that $q equiv a mod b$.

Must $lambda(alpha)=lambda_{a,b}(alpha), M(alpha)=M_{a,b}(alpha)$? If not, are there quantitative estimates on how “bad” $lambda_{a,b}(alpha)$ or $M_{a,b}(alpha)$ can get?

A simple solution to problems like this is to simply consider the sequence of continued fraction convergents, and check whether the reduced denominators fall into any given residue class infinitely many times. In the case where $a=1$, $b=2$ (i.e., when we want $q$ odd), it is easy, since consecutive denominators in the convergents are necessarily coprime, hence we cannot have consecutive even denominators, hence we have infinitely many odd denominators. However, I’m not sure how to go about attacking the general problem.

Tagged : / /

Math Genius: Prove that $gcdleft(n^{a}+1, n^{b}+1right)$ divides $n^{gcd(a, b)}+1$

Original Source Link

Let $a$ and $b$ be positive integers. Prove that $operatorname{gcd}left(n^{a}+1, n^{b}+1right)$ divides $n^{operatorname{gcd}(a, b)}+1$.

My work

I proved this for $n=2$ but I am not able to prove this for all $n$ (if anyone wants I can give my proof for $n=2$).

More Observation.

If $a$ and $b$ are both odd, then $d=gcd(a,b)$ is an odd positive integer. Therefore,
$$n^a+1=(n^d+1)left(n^{d(a-1)}-n^{d(a-2)}+ldots-n^d+1right)$$
and
$$n^b+1=(n^d+1)left(n^{d(b-1)}-n^{d(b-2)}+ldots-n^d+1right),$$
whence $n^d+1$ divides both $n^a+1$ and $n^b+1$. That is, $n^d+1$ divides $gcd(n^a+1,n^b+1)$. However, we can perform Euclidean algorithm as follows.

Without loss of generality, let $ageq b$.

Case I: $ageq 2b$. We have
$$n^a+1=(n^{b}+1)left(n^{a-b}-n^{a-2b}right)+(n^{a-2b}+1),.$$
We can replace $(a,b)$ by $(a-2b,b)$, and perform more reduction steps.

Case II: $b<a<2b$. We have
$$n^{a}+1=(n^b+1)n^{a-b}-left(n^{a-b}-1right)$$
and
$$n^b+1=left(n^{a-b}-1right)n^{2b-a}+(n^{2b-a}+1),.$$
Thus, we can replace $(a,b)$ by $(b,2b-a)$ and perform more reduction steps.

Case III: $a=b$. Then, the reduction steps end.

Note that, at each step, the difference between $a$ and $b$ never increases. (Observe that, we cannot perform the steps in Case II infinitely many times, as the smaller value between $a$ and $b$ always decreases.) Therefore, the process has to stop when both numbers become the same odd integer $s$, which is an integer combination of $a$ and $b$. However, $d$ divides any integer combination of (the starting values of) $a$ and $b$. Thus, $d$ divides $s$. The Euclidean algorithm above shows that $n^s+1$ is the greatest common divisor of $n^a+1$ and $n^b+1$. Thus, $s=d$, so in the case $a$ and $b$ are odd,
$$gcd(n^a+1,n^b+1)=n^{gcd(a,b)}+1,.$$

Let $mathrm{WLOG}$ $a>b$. For any prime $p$ let $v_p(m)$ denotes the maximum exponent of $p$ in the canonical prime factorisation of $m$. We need to show that $$v_p(mathrm{gcd}(n^a+1,n^b+1))leq v_p(n^{mathrm{gcd}(a,b)}+1)$$ For all primes $p$. If $v_p(n^{mathrm{gcd}(a,b)}+1)=0$, then it’s your exercise why $p$ doesn’t divide $mathrm{gcd}(n^a+1,n^b+1)$. Now let $$v_p(mathrm{gcd}(n^a+1,n^b+1))=alpha,.$$ Then $p^{alpha}mid (n^a+1)$ and $p^{alpha}mid(n^b+1)$. Therefore, $$p^{alpha}mid n^a-n^b= n^b(n^{a-b}-1),.$$ Since $p>1$, $mathrm{gcd}(n,p)=1$. Then, $p^{alpha}mid (n^{a-b}-1)$. Similarly we get, $$p^{alpha}mid (n^{a-b}-1)+(n^b+1)=n^b(n^{a-2b}+1),.$$

Then as before, $p^{alpha}mid(n^{a-2b}+1)$.

In this way you can reach $mathrm{gcd}(a,b)$ in the exponent like we get gcd of two integers by Euclidean algorithm.

Hence finally you will conclude that $p^{alpha}mid (n^{mathrm{gcd}(a,b)}+1)$. Hence $v_p(n^{mathrm{gcd}(a,b)}+1)geq alpha$.

Done!

Suppose that for some prime $p$ and positive integer $k$ we have $p^k$ divides both $n^a+1$ and $n^b+1$. Then, we need to prove that $p^k$ divides $n^{gcd(a,b)}+1$. Denote $d=gcd(a,b)$. Here, we will consider two cases:

Case 1. $p=2$. In this case, if $a$ or $b$ is even, then $k=1$ (because $m^2+1$ can’t be divisible by 4) and $n$ should be odd. So, $n^d-1$ is divisible by $p^k=2$, as desired.

If both $a$ and $b$ is odd, then $gcd(n^a+1, n^b+1)=n^d+1$ (it’s similar to Prove that $gcd(a^n – 1, a^m – 1) = a^{gcd(n, m)} – 1$) and in particular, $2^kmid n^d+1$.

Case 2. $p>2$. In this case, note that $p^k$ divides $$n^{2a}-1=(n^a-1)(n^a+1)$$ and $$n^{2b}-1=(n^b-1)(n^b+1),,$$ so $p^k$ divides $n^{2d}-1=(n^d-1)(n^d+1)$. Note that $p$ can’t divide both $n^d-1$ and $n^d+1$ (because $p>2$). Hence, it’s sufficient to prove that $n^d-1$ can’t be divisible by $p^k$. Indeed, if $n^dequiv 1pmod {p^k}$, then $$n^aequiv n^bequiv 1pmod {p^k},.$$ However, by our assumption we have $n^aequiv n^bequiv -1pmod {p^k}$, so due to $p^k>2$ we get a contradiction. Thus, $p^k$ divides $n^d+1$ as desired.

Tagged : / / /

Math Genius: Unique solution of the equation $prod_{i=1}^m(a_i+1)prod_{i=1}^n(b_i)=prod_{i=1}^m(a_i)prod_{i=1}^n(b_i+1)$

Original Source Link

Let $a_i$ be a sequence of $m$ distinct odd integers and $b_i$ a sequence of $n$ distinct odd integers.

We have to prove that,
$$prod_{i=1}^m(a_i+1)prod_{i=1}^n(b_i)=prod_{i=1}^m(a_i)prod_{i=1}^n(b_i+1)$$ has only one solution: $n=m$ with $a_i=b_i$ for $1le ile n$ (neglecting the sorting of sequence members).

For a disproof a counterexample is sufficient:
The both sequences $(a_1,a_2,a_3)=(135,85,215)$ and $(b_1,b_2,b_3)=(65,165,415)$ satisfy the introduced product equality:

$136cdot86cdot216cdot65cdot165cdot415=135cdot85cdot215cdot66cdot166cdot416$

Another example are the sequences $(a_1,a_2)=(4887,110591)$ and $(b_1,b_2)=(6335,17919)$:

$4888cdot110592cdot6335cdot17919=4887cdot110591cdot6336cdot17920$

Tagged : / / / /

Math Genius: Prove that $gcdleft(n^{a}+1, n^{b}+1right)$ divides $n^{gcd(a, b)}+1$

Original Source Link

Let $a$ and $b$ be positive integers. Prove that $operatorname{gcd}left(n^{a}+1, n^{b}+1right)$ divides $n^{operatorname{gcd}(a, b)}+1$.

My work

I proved this for $n=2$ but I am not able to prove this for all $n$ (if anyone wants I can give my proof for $n=2$).

More Observation.

If $a$ and $b$ are both odd, then $d=gcd(a,b)$ is an odd positive integer. Therefore,
$$n^a+1=(n^d+1)left(n^{d(a-1)}-n^{d(a-2)}+ldots-n^d+1right)$$
and
$$n^b+1=(n^d+1)left(n^{d(b-1)}-n^{d(b-2)}+ldots-n^d+1right),$$
whence $n^d+1$ divides both $n^a+1$ and $n^b+1$. That is, $n^d+1$ divides $gcd(n^a+1,n^b+1)$. However, we can perform Euclidean algorithm as follows.

Without loss of generality, let $ageq b$.

Case I: $ageq 2b$. We have
$$n^a+1=(n^{b}+1)left(n^{a-b}-n^{a-2b}right)+(n^{a-2b}+1),.$$
We can replace $(a,b)$ by $(a-2b,b)$, and perform more reduction steps.

Case II: $b<a<2b$. We have
$$n^{a}+1=(n^b+1)n^{a-b}-left(n^{a-b}-1right)$$
and
$$n^b+1=left(n^{a-b}-1right)n^{2b-a}+(n^{2b-a}+1),.$$
Thus, we can replace $(a,b)$ by $(b,2b-a)$ and perform more reduction steps.

Case III: $a=b$. Then, the reduction steps end.

Note that, at each step, the difference between $a$ and $b$ never increases. (Observe that, we cannot perform the steps in Case II infinitely many times, as the smaller value between $a$ and $b$ always decreases.) Therefore, the process has to stop when both numbers become the same odd integer $s$, which is an integer combination of $a$ and $b$. However, $d$ divides any integer combination of (the starting values of) $a$ and $b$. Thus, $d$ divides $s$. The Euclidean algorithm above shows that $n^s+1$ is the greatest common divisor of $n^a+1$ and $n^b+1$. Thus, $s=d$, so in the case $a$ and $b$ are odd,
$$gcd(n^a+1,n^b+1)=n^{gcd(a,b)}+1,.$$

Let $mathrm{WLOG}$ $a>b$. For any prime $p$ let $v_p(m)$ denotes the maximum exponent of $p$ in the canonical prime factorisation of $m$. We need to show that $$v_p(mathrm{gcd}(n^a+1,n^b+1))leq v_p(n^{mathrm{gcd}(a,b)}+1)$$ For all primes $p$. If $v_p(n^{mathrm{gcd}(a,b)}+1)=0$, then it’s your exercise why $p$ doesn’t divide $mathrm{gcd}(n^a+1,n^b+1)$. Now let $$v_p(mathrm{gcd}(n^a+1,n^b+1))=alpha,.$$ Then $p^{alpha}mid (n^a+1)$ and $p^{alpha}mid(n^b+1)$. Therefore, $$p^{alpha}mid n^a-n^b= n^b(n^{a-b}-1),.$$ Since $p>1$, $mathrm{gcd}(n,p)=1$. Then, $p^{alpha}mid (n^{a-b}-1)$. Similarly we get, $$p^{alpha}mid (n^{a-b}-1)+(n^b+1)=n^b(n^{a-2b}+1),.$$

Then as before, $p^{alpha}mid(n^{a-2b}+1)$.

In this way you can reach $mathrm{gcd}(a,b)$ in the exponent like we get gcd of two integers by Euclidean algorithm.

Hence finally you will conclude that $p^{alpha}mid (n^{mathrm{gcd}(a,b)}+1)$. Hence $v_p(n^{mathrm{gcd}(a,b)}+1)geq alpha$.

Done!

Suppose that for some prime $p$ and positive integer $k$ we have $p^k$ divides both $n^a+1$ and $n^b+1$. Then, we need to prove that $p^k$ divides $n^{gcd(a,b)}+1$. Denote $d=gcd(a,b)$. Here, we will consider two cases:

Case 1. $p=2$. In this case, if $a$ or $b$ is even, then $k=1$ (because $m^2+1$ can’t be divisible by 4) and $n$ should be odd. So, $n^d-1$ is divisible by $p^k=2$, as desired.

If both $a$ and $b$ is odd, then $gcd(n^a+1, n^b+1)=n^d+1$ (it’s similar to Prove that $gcd(a^n – 1, a^m – 1) = a^{gcd(n, m)} – 1$) and in particular, $2^kmid n^d+1$.

Case 2. $p>2$. In this case, note that $p^k$ divides $$n^{2a}-1=(n^a-1)(n^a+1)$$ and $$n^{2b}-1=(n^b-1)(n^b+1),,$$ so $p^k$ divides $n^{2d}-1=(n^d-1)(n^d+1)$. Note that $p$ can’t divide both $n^d-1$ and $n^d+1$ (because $p>2$). Hence, it’s sufficient to prove that $n^d-1$ can’t be divisible by $p^k$. Indeed, if $n^dequiv 1pmod {p^k}$, then $$n^aequiv n^bequiv 1pmod {p^k},.$$ However, by our assumption we have $n^aequiv n^bequiv -1pmod {p^k}$, so due to $p^k>2$ we get a contradiction. Thus, $p^k$ divides $n^d+1$ as desired.

Tagged : / / /

Math Genius: Alternate proof that $exists x in Bbb{Z}$ such that $ gcd (a+bx,c) = 1$?

Original Source Link

I came across this question in the book An Excursion in Mathematics:

Let $a,b,c in Bbb{Z}$ such that $gcd(a,b) =1, c>0$. Prove that $exists x in Bbb{Z}$ such that $ gcd (a+bx,c) = 1$.

There is one proof that is easy enough: By Dirichlet’s Theorem, there are infinitely many primes of the form $a+bx$ where $a,b$ are relatively prime, so we merely take the first prime of the form $a+bx>c$.

On the other hand, however, the book is a fairly elementary textbook on high-school math contests and Dirichlet’s theorem is not mentioned. I am having difficulty coming up with another proof for this. I have tried to construct an $x$ such that $a+bx$ is relatively prime to $c$, but to no avail.

How would I proceed towards the proof?

Consider a prime factor $p$ of $c$. Then if $pmid b$, $pnmid a$
and all $x$ satisfy $a+bxnotequiv0pmod p$. If $pnmid b$ the solutions
to $a+bxequiv1pmod p$ form a conguruence class modulo $p$.

All one needs is to choose $x$ so that $a+bxequiv1pmod p$ for all primes
$pmid c$, $pnmid b$. Now use Chinese Remainder Theorem.

Tagged : /

Math Genius: Alternate proof that $exists x in Bbb{Z}$ such that $ gcd (a+bx,c) = 1$?

Original Source Link

I came across this question in the book An Excursion in Mathematics:

Let $a,b,c in Bbb{Z}$ such that $gcd(a,b) =1, c>0$. Prove that $exists x in Bbb{Z}$ such that $ gcd (a+bx,c) = 1$.

There is one proof that is easy enough: By Dirichlet’s Theorem, there are infinitely many primes of the form $a+bx$ where $a,b$ are relatively prime, so we merely take the first prime of the form $a+bx>c$.

On the other hand, however, the book is a fairly elementary textbook on high-school math contests and Dirichlet’s theorem is not mentioned. I am having difficulty coming up with another proof for this. I have tried to construct an $x$ such that $a+bx$ is relatively prime to $c$, but to no avail.

How would I proceed towards the proof?

Consider a prime factor $p$ of $c$. Then if $pmid b$, $pnmid a$
and all $x$ satisfy $a+bxnotequiv0pmod p$. If $pnmid b$ the solutions
to $a+bxequiv1pmod p$ form a conguruence class modulo $p$.

All one needs is to choose $x$ so that $a+bxequiv1pmod p$ for all primes
$pmid c$, $pnmid b$. Now use Chinese Remainder Theorem.

Tagged : /

Math Genius: Alternate proof that $exists x in Bbb{Z}$ such that $ gcd (a+bx,c) = 1$?

Original Source Link

I came across this question in the book An Excursion in Mathematics:

Let $a,b,c in Bbb{Z}$ such that $gcd(a,b) =1, c>0$. Prove that $exists x in Bbb{Z}$ such that $ gcd (a+bx,c) = 1$.

There is one proof that is easy enough: By Dirichlet’s Theorem, there are infinitely many primes of the form $a+bx$ where $a,b$ are relatively prime, so we merely take the first prime of the form $a+bx>c$.

On the other hand, however, the book is a fairly elementary textbook on high-school math contests and Dirichlet’s theorem is not mentioned. I am having difficulty coming up with another proof for this. I have tried to construct an $x$ such that $a+bx$ is relatively prime to $c$, but to no avail.

How would I proceed towards the proof?

Consider a prime factor $p$ of $c$. Then if $pmid b$, $pnmid a$
and all $x$ satisfy $a+bxnotequiv0pmod p$. If $pnmid b$ the solutions
to $a+bxequiv1pmod p$ form a conguruence class modulo $p$.

All one needs is to choose $x$ so that $a+bxequiv1pmod p$ for all primes
$pmid c$, $pnmid b$. Now use Chinese Remainder Theorem.

Tagged : /

Math Genius: A question about the probability of being a prime?

Original Source Link

If we chose a random number $a leq N$, then, the probability for $a$ to be a prime is $frac{1}{log N}$.

Now, if there are some primes that do not divide $a$, then what is the probability for $a$ to be a prime?

EX: if $a leq 100000$, and both of {2,3,5,7} don’t divide $a$, then what is the probability for $a$ to be a prime?

First off, the result that the density of the primes is $frac{1}{ln N}$ is asymptotic, as in it holds as a limit (so asking specifically $aleq10^5$ means you get an approximation to the true answer).

Next, simply notice that for sufficiently large $N$, we have that $frac{1}{2}$ of numbers are not divisible by $2$, $frac{2}{3}$ are not divisible by $3$, etc. These are all independent for sufficiently large $N$.

So, the count of numbers below $N$ that are not divisible by $P={2,3,5,7}$ is just
$$Nprod_{pin P}left(1-frac{1}{p}right)text{.}$$

The numerator, the number of primes that are not in $P$, is even easier: there are $Omega(N/ln(N))$ total primes, minus all $left|Pright|=4$ forbidden ones.

The answer is
$$frac{frac{N}{ln(N)}-left|Pright|}{Nprod_{pin P}left(1-frac{1}{p}right)}$$

Tagged : / / /

Math Genius: Alternate proof that $exists x in Bbb{Z}$ such that $ gcd (a+bx,c) = 1$?

Original Source Link

I came across this question in the book An Excursion in Mathematics:

Let $a,b,c in Bbb{Z}$ such that $gcd(a,b) =1, c>0$. Prove that $exists x in Bbb{Z}$ such that $ gcd (a+bx,c) = 1$.

There is one proof that is easy enough: By Dirichlet’s Theorem, there are infinitely many primes of the form $a+bx$ where $a,b$ are relatively prime, so we merely take the first prime of the form $a+bx>c$.

On the other hand, however, the book is a fairly elementary textbook on high-school math contests and Dirichlet’s theorem is not mentioned. I am having difficulty coming up with another proof for this. I have tried to construct an $x$ such that $a+bx$ is relatively prime to $c$, but to no avail.

How would I proceed towards the proof?

Consider a prime factor $p$ of $c$. Then if $pmid b$, $pnmid a$
and all $x$ satisfy $a+bxnotequiv0pmod p$. If $pnmid b$ the solutions
to $a+bxequiv1pmod p$ form a conguruence class modulo $p$.

All one needs is to choose $x$ so that $a+bxequiv1pmod p$ for all primes
$pmid c$, $pnmid b$. Now use Chinese Remainder Theorem.

Tagged : /

Math Genius: Express $ operatorname{gcd}left(5^{m}+7^{m}, 5^{n}+7^{n}right) $ in terms of $m$ and $n$

Original Source Link

Let $m$ be a positive integer with $operatorname{gcd}(m, n)=1 .$ Express
$
operatorname{gcd}left(5^{m}+7^{m}, 5^{n}+7^{n}right)
$

in terms of $m$ and $n$

My work

let $d=operatorname{gcd}(5^m +7^m,5^n +7^n)$ then

$5^{2m} equiv 7^{2m}$ mod(d)

$5^{2n} equiv 7^{2n}$ mod(d)

and obviously $gcd(5,d)=gcd(7,d)=1$ so,

$5^{gcd(2m,2n)} equiv 7^{gcd(2m,2n)}$ (mod d)

$5^2 equiv 7^2$ (mod d)

$d= 1,2,3,4,6,8,12,24$

now i find values of d how to express this in terms of $m$ and $n$ ???

Case $,a,b = 5,7,$ below [homogenization of this], which applies $color{#90f}{rm E} = $ Euclid’s algorithm,
e.g. $$(a_1,a_2,b) overset{color{#90f}{rm E}}= (bar a_1,bar a_2,b), {rm if}, {a_iequiv bar a_i}!!! pmod{!b}, text{is used in the first line of the proof}$$

Theorem $ $ If $, m,ninBbb N, $ $(m,n)!=!1!=!(a,b),,$
and wlog $,m !=! 1!+!2j,$ is odd, then

$$ d := (a^{large m}!+!b^m,a^{large n}!+!b^{large n})= (a!+!b,color{#0a0}{(-!1)^{large n}!+!1})
=begin{cases} (a!+!b,2) {rm if}, 2mid n\ (a!+!b)quad , {rm if} 2nmid !nend{cases}qquad $$

Proof $ bmod d!: b^{-1},$ exists by $,(d,b) overset{color{#90f}{rm E}}= (a^m,a^n,b)=1,$ by $,(a,b)=1.,$ Let $,c equiv a/b:= ab^{-1}$.
Then $, {c^{large m}}^{phantom{|^|}}!!!equiv -1equiv c^{large n}Rightarrow c^{large 2m}equiv 1equiv c^{large 2n}$ so $,{rm ord}, c^{large 2}$ divides coprimes $m,n$ so is $1,,$ so $,color{#c00}{c^{large 2}equiv 1}.,$ $,{-}1equiv c^{large m}!equiv c^{largephantom{,}}!(color{#c00}{c^{large 2}})^{large j}!equiv c,$ $Rightarrow,c!+!1equiv 0,overset{times b}Rightarrow,a!+!bequiv 0,$ so $,d overset{color{#90f}{rm E}}= (a!+!b,d) overset{color{#90f}{rm E}}= (a!+!b,,color{#0a0}{dbmod a!+!b}),$ is as claimed, by $!bmod{,color{#0a0}{!a!+!b}}!: underbrace{a^{large k}!+!b^k equiv b^k(color{#0a0}{(-1)^{large k}!+!1})}_{large color{#0a0}{ a ,equiv -b} }^{phantom .},$ and $,(d,b^kcolor{#0a0}e)=(d,color{#0a0}e),$ by $,(d,b)=1$.


Remark $ $ We can easily extend the above to the case when $,m,n,$ are not coprime.

Corollary $ $ If $,(A,B)=1,$ and $,M,Nin Bbb N,,$ and wlog $,M/(M,N),$ is odd, then

$quad(A^M!+!B^M,A^N!+!B^N), =, (A^{(M,N)}!+!B^{(M,N)},C),, begin{cases} C = 2 {rm if} 2mid N/(M,N)\ C = 0 {rm otherwise}end{cases}$

Proof $ $ Let $,D = (M,N),, a = A^D, b = B^D.,$ Then $,(m,n) := (M/D,:! N/D) = 1,$ and

$quadbegin{align} (A^{M}!+!B^{M},A^{N}!+!B^{N}), &=, {(A^{Dlarge m}!+!B^{Dlarge m},(A^{Dlarge n}!+!B^{Dlarge n})}\[.2em]
&=,{ (a^{large m} + b^{large m},, a^{large n} + b^{large n})}end{align} $
so the Theorem applies.

For $k$ odd we have that
$$5^k+7^kequiv 0mod 3$$
and
$$5^k+7^kequiv 5+7equiv 4mod 8$$

For $k$ even we have that
$$5^k+7^kequiv 2mod 3$$
and
$$5^k+7^kequiv 1+1equiv 2mod 8$$

From here we have that if $m,n$ are both odd(i.e. if $m+n$ is even), then $gcd(5^m+7^m,5^n+7^n)=12$.
Otherwise, if between $m$ and $n$ there is an odd and an even number(i.e. if $n+m$ is odd), then $gcd(5^m+7^m,5^n+7^n)=2$.

So, for $gcd(m,n)=1$, you could express
$$gcd(5^m+7^m,5^n+7^n)=2cdot
3^{(m+n+1)%2}cdot 2^{(m+n+1)%2}$$

Where $a%b$ denotes the remainder that we obtain when dividing $a÷b$.

Ps. This is clearly not a favorable answer since it doesn’t seem generalizable.

When $m$ and $n$ are both odd and coprime and $a,b$ are coprime, $gcd(a^m + b^m, a^n + b^n) = a + b$.

As stated by @Geoffrey in the comments, $a+b mid a^k + b^k$ for odd $k$:

$$a^m+b^m = (a + b)underbrace{(a^{m-1} – a^{m-2}b + a^{m-3}b^{2} – dots + b^{m-1})}_{mspace terms}$$
$$a^n+b^n = (a + b)underbrace{(a^{n-1} – a^{n-2}b + a^{n-3}b^{2} – dots + b^{n-1})}_{nspace terms}$$

The rightmost polynomials in both equations have no common factor since $m$ and $n$ have no common factor.

If $m,n$ are both even, then they cannot be coprime. If one of $m, n$ is even, then…?

Tagged : / / /