Compute gcd$ \ (7^{n} + 4, \ 7^{n})$

Question

Question:

Compute gcd$ \ (7^{n} + 4, \ 7^{n})$ where $ \ n \in \mathbb{N}$ using the Euclidean algorithm.

My attempt:

We first have to write it in the form $\ a = bq +r$ where $ q \ge 0,\ 0 \le r \lt b$

$ a = 7^{n} + 4$

$b = 7^{n}$

Step $1$:

$ 7^{n} + 4 = 7^{n}. 1 + 4$

Step $2$:

$ 7^{n} = 4.q + r $

I can't seem to find new $ \ q,r$ in the second step

Answer 1

The Euclidean algorithm yields the GCD as the last non-zero remainder. (I assume you are familiar with this) I'll continue where you got stuck: $$7^n = 4q + r, 0\leq r<4 $$ If $r=0$, then $7^n$ would be divisible by $4$, which is nonsense. So $r\in\{1,2,3\}$

Suppose $r=3$, then $7^n = 4q + 3$, for some $q\in\mathbb Z$ and $\mbox{gcd}(4,3)=1$, so $\mbox{gcd}(7^n+4,7^n)=1$.
Apparently, $r=2$ is impossible. In any event, the greatest common divisor must be $1$.

Answer 2

I don't know why you insist on using the Euclidean algorithm. The following is how I would try the problem anyway.

Let $d=\gcd(7^n+4,7^n)$. Then $d\mid 7^n+4$ and $d\mid 7^n$. So $d\mid 7^n+4-7^n$, i.e. $d\mid4 $. So $d=1,2,$ or $4$. If $d=2$ then $2\mid 7^n$ which is impossible since $7^n$ is odd. Similarly reject the choice $d=4$. So $d=1$.

Answer 3

The GCD you're looking for is the largest positive integer which divides both $7^n$ and $7^n+4$. Focus on the $7^n$ first; what's the only form of number which can divide this? A power of $7$, with the power being less than or equal to $n$.

Now, amongst these possibilities, which of these could possibly divide $7^n+4$?

Answer 4

By the Euclidean algorithm steps you have already laid out, $\gcd(7^n+4, 7^n) = \gcd(7^n, 4)$. Since $7^n$ is odd and $4$ is a power of two, their gcd must be $1$.

Answer 5

\begin{align} 7^n + 4 &= 1 \cdot 7^n + 4 \\ 7^n &= \frac{7^n -d}{4} \cdot 4 + d \end{align} where if $n$ is even then $7^n \equiv 1 \pmod 4$ so $d = 1$ and $\gcd(7^n + 4, 7^n) = 1$.

If $n$ is odd then $7^n \equiv 3 \pmod 4$ so $d = 3$ and we have $$ 4 = 1 \cdot 3 + 1 $$ which again gives $\gcd(7^n + 4, 7^n) = 1$.

Answer 6

This can be done without recourse to the mod function.

Define $A_{2k} = \frac 14(7^{2k}-1)$ and $A_{2k+1} = \frac 14(7^{2k+1}+1)$

It isn't too much work to show that $A_n \in \mathbb Z$ for all $n \in \mathbb N$.

For $n$ even $$-(7^n + 4)A_n + 7^n(A_n+1) = 7^n-4A_n = 1$$

For $n$ odd $$(7^n + 4)A_n - 7^n(A_n+1) = 4A_n - 7^n = 1$$

It follows that, for all $n \in \mathbb N, \; \gcd(7^n+4, 7^n)=1$

$7^{2k}-1$ is a multiple of $4$

It's true for $k=0: \qquad 7^0-1 = 0 = 4\cdot 0 $

If it's true for $k=\ell$, then it's true for $k=\ell + 1$:

$\qquad \text{Suppose} \; 7^{2\ell}-1 = 4N.$

$\qquad \text{Then} \; 7^{2\ell+2}-1 = 49 \cdot 7^{2\ell}-1 = 49(4N+1)-1 = 4(49N+12).$

$7^{2k+1}+1$ is a multiple of $4$

$\qquad 7^{2k+1}+1 = (7+1)(1 + 7 + 7^2 + \cdots + 7^{2k}) \; \text{is a multiple of $4$}$

For example

\begin{align} 7^3 &= 343 \\ A_3 &= \frac 14(7^3+1) = 86 \\ 1 &= 86 \color{red}{(7^3+4)} - 87\color{red}{(7^3)} \end{align}

and

\begin{align} 7^4 &= 2401 \\ A_4 &= \frac 14(7^4-1) = 600 \\ 1 &= -600 \color{red}{(7^4+4)} + 601\color{red}{(7^4)} \end{align}