+0

# The Euclidean Algorithm and 100 Headaches

-1
70
3

(deleted)

Apr 29, 2020
edited by somehelpplease  May 8, 2020

#1
+1

We can use Euclid's algorithm for a few steps:

gcd(2𝑎2+29𝑎+65,𝑎+13)=gcd(2𝑎2+29𝑎+65−2𝑎(𝑎+13),𝑎+13)=gcd(3𝑎+65,𝑎+13)=gcd(3𝑎+65−3(𝑎+13),𝑎+13)=gcd(26,𝑎+13)gcd(2a2+29a+65,a+13)=gcd(2a2+29a+65−2a(a+13),a+13)=gcd(3a+65,a+13)=gcd(3a+65−3(a+13),a+13)=gcd(26,a+13)

which is necessarily 1,2,131,2,13 or 2626, just by looking at the first term. By factoring 11831183, and considering that 𝑎a is an odd multiple, you should be able to conclude the rest

I'm sorry for the bad spacing I wrote this in apple notes and copy-pasted

Here to help

:D

Apr 29, 2020

#1
+1

We can use Euclid's algorithm for a few steps:

gcd(2𝑎2+29𝑎+65,𝑎+13)=gcd(2𝑎2+29𝑎+65−2𝑎(𝑎+13),𝑎+13)=gcd(3𝑎+65,𝑎+13)=gcd(3𝑎+65−3(𝑎+13),𝑎+13)=gcd(26,𝑎+13)gcd(2a2+29a+65,a+13)=gcd(2a2+29a+65−2a(a+13),a+13)=gcd(3a+65,a+13)=gcd(3a+65−3(a+13),a+13)=gcd(26,a+13)

which is necessarily 1,2,131,2,13 or 2626, just by looking at the first term. By factoring 11831183, and considering that 𝑎a is an odd multiple, you should be able to conclude the rest

I'm sorry for the bad spacing I wrote this in apple notes and copy-pasted

Here to help

:D

LuckyDucky Apr 29, 2020
#2
+1

Haha, nah it's fine. Thanks for helping :D