1

Let n be an arbitrary positive integer. Express $\gcd(8n + 3, 5n - 2)$ as a function of $n$.

Is the answer so trivial that all you need to do it multiply it out using EEA?

So would $f(n) = (8n+3)x + (5n - 2)y$ work?

Tim Ratigan
  • 7,247
user242743
  • 175
  • 3
  • 6

2 Answers2

2

Yes, minimizing $(8n+3)x+(5n-2)y$ would work. Note $(8n+3)(5)+(5n-2)(-3)=21$, so $\gcd(8n+3,5n-2)|21$. $8n+3\equiv 2n\pmod 3$, $5n-2\equiv 2n+1\pmod 3$, so both expressions are not divisible by $3$.

Let's try solving $\pmod 7$: $$ 8n+3\equiv 5n-2\pmod 7\\\Longrightarrow n\equiv 3\pmod 7 $$ Evidently, they cannot both be divisible by $7$, either. Therefore they are coprime.

Tim Ratigan
  • 7,247
0

If you defined $x$ and $y$ in a suitable way, you could express the answer like that, but your homework would probably want you to write $x$ and $y$ as 'explicit' functions of $n$.

It would be easier to just use the Euclidean algorithm, since you don't actually need to write the answer as a linear combination of $8n+3$ and $5n-2$.