Largest greatest common divisor

This question asks what is the largest X such that:

$8n + 7 \equiv 0 \pmod {x} \\ 5n + 6 \equiv 0 \pmod{x}$

Applying modular arithmetic , we get that

$0 \equiv ( 8n + 7 ) + ( 5n + 6 ) = 13 n + 13 = 13 (n+1 ) \pmod{x}$

Since we know that $\gcd( n+ 1, 5n+6 ) = \gcd ( n+1, 1 )$ , hence the largest GCD that is possible is 13.

This occurs when $n = 4$ , which gives us $5n + 6 = 26$ and $8n + 7 = 39$ .

Using the Euclidean Algorithm, $\begin{aligned} \gcd(5n+6,8n+7)&=\gcd(5n+6,3n+1) \\ &=\gcd(2n+5,3n+1) \\ &=\gcd(2n+5,n-4) \\ &=\gcd(n+9,n-4) \\ &=\gcd(13,n-4) \end{aligned}$ Therefore, the greatest common divisor must be a factor of 13, the largest of which is $\boxed{13}$ . The maximum is achieved, for example, when $n=17$ , as $\gcd(13,26)=13$ .

This question is a direct application of the Euclidean Algorithm. We can continue to simplify the equation which expresses the $GCD$ of the 2 binomials until we get something we can work with.

$8n + 7 = 1 \times (5n + 6) + (3n +1)$

$5n + 6 = 1 \times (3n + 1) + (2n + 5)$

$3n + 1 = 1 \times (2n + 5) + (n - 4)$

$2n + 5 = 2 \times (n - 4) + (13)$

Now that we have simplified the expression for the GCD of the two binomials, we can rewrite it.

$GCD(8n + 7, 5n + 6) = GCD(n - 4, 13)$

We want to find the maximum value for $n$ such that $n - 4$ shares a common factor with $13$ .

The maximum possible value for $n$ can be found this way by setting $n - 4$ equal to $13$ .

Therefore, $n = 17$ and the greatest possible value for the GCD is $\boxed{13}$ .

Given that the number x we are searching for is a G.C.D., it divides 5n+6 and 8n+7. This mathematically speaking means that there are two, possibly, different numbers m and L such that mx = 5n + 6 and Lx = 8n +7. Solve for n in each equation and compare both values: n=(mx-6)/5=(Lx-7)/8. From here, by solving for x we get to the equation x(8y-5z)=13. This is telling us that whatever number x is, it must divide 13 also. Due to the fact that the other factor must be positive given that x is positive and that 13 is only divisible by the positive integers 13 and 1. It must be then that the x is the greatest of the two. Hence x is 13.

By using Euclidean algorithm, we get

$gcd(5n+6 , 8n+7)$

$=$ $gcd(5n+6 , 3n+1)$

$=$ $gcd(2n+5 , 3n+1)$

$=$ $gcd(2n+5 , n-4)$

$=$ $gcd(n+9 , n-4)$

$=$ $gcd(13 , n-4)$

From here, we can say that $13|n-4$ , or else the gcd would be $1$ .Therefore the largest possible value is $\boxed {13}$

Applying the Euclidean Algorithm again and again, we can reach our desired answer... $(a,b)$ means the greatest common divisor of $a$ and $b$ ...

$(8n+7, ~5n+6)$

$= (5n+6, ~3n+1)$

$= (3n+1, ~2n+5)$

$= (2n+5, ~n-4)$

$= (n-4, ~13)$

Hence, the largest possible value is $\fbox{13}$ ...

Remark: The largest value is attained for any multiple of $13$ and so $n-4=13m$ for some integer $m$ ...

Let, $d=\gcd(5n+6,8n+7)=\gcd(5m+1,8m-1)$ where $m=n+1$ . Now, we observe that $8(5m+1)-5(8m-1)=13\Rightarrow d|13\Rightarrow d=1 \ \mbox{or,} \ 13$ . A simple check now reveals that for $m=5,\ d=13$ . So $\boxed{13}$ is the answer.

We use Euler's algorithim for calculating GCD's. $\gcd (5n+6, 8n+7)$ $= \gcd (5n+6, 3n+1)$ $= \gcd (2n+5, 3n+1)$ $= \gcd (2n+5, n-4)$ $= \gcd (n+9, n-4)$ $= \gcd (13, n-4)$ Since the GCD cannot be greater than the absolute value of any of the integers themselves, we know that the GCD cannot be greater than $13$ .

A quick test reveals that a GCD of $13$ is indeed possible with $n = 4$ , so the answer is thus $\boxed{13}$ .

I solved this problem by Euclidean Algorithm.

By Euclidean Algorithm to calculate $gcd(8n+7,5n+6)$ ,

$8n+7=(5n+6)+(3n+1)$

$5n+6=(3n+1)+(2n+5)$

$3n+1=(2n+5)+(n-4)$

$2n+5=2(n-4)+13$

Interestingly, we get a beautiful number $13$ which is the answer we want!

• Let d = gcd(5n + 6, 8n + 7) then d = gcd(40n + 48, 40n + 35) = gcd (13, 40n + 35) = 13 since 13 is a prime number

Let the g.c.d. be $x$ .

$5n - 6 \equiv 0 \mod x$

$\implies 5n \equiv 6 \mod x$

$\implies 40n \equiv 48 \mod x$

$8n - 7 \equiv 0 \mod x$

$\implies 8n \equiv 7 \mod x$

$\implies 40n \equiv 35 \mod x$

So, $48 \equiv 35 \mod x$

Now, $48 - 13 = 35$

$\therefore x = \boxed{13}$

If d is a common divisor of 8n+7 and 5n+6. Then It is a divisor of 8(5n+6) - 5(8n+7) = 13. Therefore, d=1$ or d=13. We are looking the largest value so d=13.

A really simple solution! Let e be the gcd of the two numbers. Since e divides both numbers, we have: 5n + 6 = e k, 8n + 7 = e m, (k and m are some integers) Multiply 1st equation by 8, 2nd by 5 and subtract 2nd from 1st. Thus, we have: 13 = e*(8k - 5m), e = 13 / (8k - 5m) The gcd e takes the largest value when the denominator is minimal. Obviously, it can't be 0, negative or fractional, then is is 1, so the largest gcd is 13 (answer).

follow euclid algorithm

The GCD of (5n + 6) and (8n + 7) can be found out by Euclids' Division Algorithm. 8n + 7 = 1 x (5n + 6) + 3n + 1

5n + 6 = 1 x (3n + 1) + 2n + 5

3n + 1 = 1 x (2n + 5) + n - 4

2n + 5 = 2 x (n - 4) + 13

As furhter division is not possible, we can say that 13 is the GCD.