A number theory problem by Ralph Macarasig

Number Theory Level 3

$\Large A =2017^{40^{640}} - 2017 \qquad \qquad B = 2017^{40^{544}} - 2017$

The greatest common divisor of $A$ and $B$ can be expressed in the form $\large 2017^{x^{y}} - 2017$ , where $x$ and $y$ are integers .

Submit your answer as $\overline{xy}$ , which is the concatenation of the digits of $x$ and $y$ . For example, if $x = 10$ and $y = 12$ , then $\overline{xy} = 1012$ .

The answer is 4032.

2 solutions

Ralph Macarasig
May 25, 2016

Relevant wiki: Greatest Common Divisor - Problem Solving

We can use the (very useful) fact that

$gcd(a^m-1, a^n-1) = a^{gcd(m,n)}-1$

Hence, $gcd(2017^{40^{640}} - 2017, 2017^{40^{544}} - 2017) =$ $2017\times gcd(2017^{40^{640}-1}-1, 2017^{40^{544}-1}-1) =$ $2017\times [2017^{gcd(40^{640}-1, 40^{544}-1)}-1] =$ $2017\times [2017^{40^{gcd(640,544)}-1}-1]$

Notice that $640 = 32\times20$ and $544 = 32\times 17$ . Since $20$ and $17$ are coprime, $gcd(640,544) = 32$ .

Therefore, $gcd(2017^{40^{640}} - 2017, 2017^{40^{544}} - 2017) =$ $2017\times[2017^{40^{32}-1}-1] =$ $2017^{40^{32}}-2017$

Hence, $x = 40$ and $y = 32$ and $\overline{xy}$ $=$ $\boxed{4032}$

Can you prove this? $\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1$

Akshat Sharda - 5 years ago

Well this is not much of proof, but here it goes.

We know that $a^m \equiv 1$ $mod$ $(a^m-1)$ and $a^n \equiv 1$ $mod$ $(a^n-1)$ .

Let $d = gcd(m,n)$ . It immediately follows that $d | m$ and $d | n$ .

$Case$ $1: m$ and $n$ are even

It follows that $d$ is also even and $a \equiv$ $\pm 1$ $mod$ $(a^m-1)$ and $a \equiv$ $\pm 1$ $mod$ $(a^n-1)$ . Hence, $a^d \equiv 1$ $mod$ $(a^m-1)$ and $a^d \equiv 1$ $mod$ $(a^n-1)$

$Case$ $2: m$ and $n$ are odd

It follows that $d$ is also odd and $a \equiv$ $1$ $mod$ $(a^m-1)$ and $a \equiv$ $1$ $mod$ $(a^n-1)$ . Hence, $a^d \equiv 1$ $mod$ $(a^m-1)$ and $a^d \equiv 1$ $mod$ $(a^n-1)$

$Case$ $3:$ One is odd and the other is even

Without loss of generality, let $m$ be odd and $n$ be even. It then follows that $d$ is odd and $a \equiv$ $1$ $mod$ $(a^m-1)$ and $a \equiv$ $\pm 1$ $mod$ $(a^n-1)$ . We may use the fact that dividing an odd integer by an odd integer yields an odd integer and that dividing an even integer by an odd integer yields an even integer. Hence, $a^d \equiv 1$ $mod$ $(a^m-1)$ and $a^d \equiv 1$ $mod$ $(a^n-1)$ .

Hence, in all cases it has been shown that $a^d - 1 \equiv 0$ $mod$ $(a^m-1)$ and $a^d - 1 \equiv 0$ $mod$ $(a^n-1)$ .

Then, any divisor of $a^m-1$ and $a^n-1$ must be a divisor of $a^d-1$ as well. Hence, $gcd(a^m-1,a^n-1) = a^{gcd(m,n)}-1$ .

Ralph Macarasig - 5 years ago

Grant Bulaong
May 25, 2016

Let $m=\frac{A}{2017}$ and $n=\frac{B}{2017}$ .

The greatest common divisor of $m$ and $n$ can be expressed in the form $2017^{x^y-1}-1$ .

$m = 2017^{40^{640}-1}-1$

Some factors of $m$ which are no less than $2016$ can be expressed in the form $2017^{\alpha_m}-1$ , where $\alpha_m$ is a factor of $40^{640}-1$ .

Next, some factors of $40^{640}-1$ which are no less than $39$ can be expressed in the form $40^{\beta}-1$ , where $\beta$ is a factor of $640$ .

Therefore, some factors of $m$ which are no less than $2017^{39}-1$ can be expressed in the form $2017^{40^{\beta}-1}-1$ .

We repeat the process for $n = 2017^{40^{544}-1}-1$ .

For $gcd(m,n)$ , we get $\beta=gcd(640,544) = 32$ , since it can be shown that no greater combination (quotient nor product) of other factors can be equal for $m$ and $n$ .

Hence, $x = 40$ , $y = 32$ and $\overline{xy}$ $=$ $\boxed{4032}$

A number theory problem by Ralph Macarasig

The answer is 4032.

2 solutions

0 pending reports