Question

Given that "a" is an odd multiple of 7767, find the greatest common divisor of 6a^2+49a+108 and 2a+9.

Answer 1

how is that?... can you detail?

Answer 2

a=(2k+1)*7767, so we want the gcd of:

6[(2k+1)*7767]^2+49(2k+1)7767 = (2k+1)*7767*(6*7767*(2k+1) + 49)

and

2(2k+1)7767

Notice that they both have (2k+1)*7767 in common, and that (6*7767*(2k+1) + 49) is an odd number. Thus, the gcd is (2k+1)*7767.

Answer 3

Ooops, I didn't write down the constants in both equations. So, I solved the wrong problem.

Answer 4

Let's try again, maybe this time with your help.

Answer 5

sure.

Answer 6

Those constants throw a monkey wrench into the works! :)

Answer 7

the answer given by loser66 is 9... but I'm waiting for explanation. not sure...if 9 is the greatest GCD.

Answer 8

Ok, a can be 9(the greatest) but how do you find it?

Answer 9

Ok, I found it.

Answer 10

So, first, expand the two equations.

Answer 11

We are given that equation one is:

6[(2k+1)7767]^2+49(2k+1)*7767+108

Answer 12

and equation two is: 2*(2k+1)*7767+9

Answer 13

ok , we can do together

Answer 14

6a^2 +49a+108 = (2a+9)(3a+11)+9

Answer 15

If we multiply these out, we get:

1447830936 k^2+1448592102 k+362338425

and

31068 k+15543

Answer 16

Now, we consider 2a+9 = ?? 9

Answer 17

Applying the gcd algorithm to all of these numbers gets you a gcd of 9.

Answer 18

Not that

Answer 19

That means you can "pull" out that 9 in both, and thus their gcd is 9.

Answer 20

2a+9 =?? 9
if a = 7761, we have 9| 2a+9,

Answer 21

so, no matter how a factor of a is, 9|2a+9

Answer 22

I know, a is an odd multiple of 7767, so the bottom line is a = 7767 and this guy divided by 9

Answer 23

We get the same answer, but I'm not following how you arrived at yours. For instance, I don't know what 9|2a+9 means.

Answer 24

I didn't get 2a+9 as the gcd, I got 9. What was the expected answer danny?

Answer 25

But I think I like your approach better, so you may be right.

Answer 26

nope, don't trust me, I don't know number theory!!

Answer 27

Oh! I got it! We can use the Euclidean Algorithm.
gcd(6a^2+49a+108,2a+9)
=gcd(6a^2+49a+108-(2a+9)(3a+11),2a+9)
=gcd(6a^2+49a+108-(6a^2+49a+99),2a+9)
=gcd(9,2a+9). Since both 2a and 9 are multiples of 9, 2a+9 is also a multiple of 9 so the greatest common divisor is 9.

Answer 28

Cool.

Answer 29

Good work.

Answer 30

hehehe... the Asker is better than the helpers!!! how ironic situation is!!

Answer 31

no, that's not the way, your answer helped me.