Question

if gcd(a,b)=1, then gcd(a,bc)=gcd(a,c)
prove

Answer 1

i write this out last last night, let me see if i can find it

Answer 2

do you know Bezout's Identity?

yo satellite :)

Answer 3

no

Answer 4

are we allowed to use bezout's identity? or the fundamental theorem of arithmetic?

Answer 5

i dont think so :)

Answer 6

then what tools do we have to work with? o.O

Answer 7

if gcd(a,c)=d and gcd(a,bc)=e then how do u prove that e|c (using gcd(a,b)=1)?

Answer 8

i think what joemath meant to ask was what theorems we allowed to use, so basically gcd characterization theorem, EEA, and basic deinitions of math

Answer 9

i guess you would just say, if (a,bc) = e, then e divides a, and e divides bc, but since (a,b) =1, e cant divide b, so it must divide c.

Answer 10

HELLO JOE!

Answer 11

but imo, that doesn't sound very concrete. A proof involving bezout or FTA would be stronger. imo anyways.

Answer 12

yo satellite!!!!!!!

Answer 13

this is what you do for this problem. i wrote it all out last night and it was late but i think i got it correct.
joe can check
long time no see!

Answer 14

Myininaya :)

/wave

Answer 15

you start with the fact that if gcd(a,b)=1 then there are integers x and y with
\[ax+by=1\] and then if gdc(a,c)= d then
\[ax_1+cy_1=d\] and then write
\[adx+bdy=d=ax_1+cy_1\]and then
\[adx+b(ax_1+cy_1)y=d\]

Answer 16

hey joe!

Answer 17

Thats what i wanted to do, but that Bezout's Identity.

Answer 18

then you write
\[a(dx+bx_1y_1)+cbyy_1\] and argue that this is a linear combination of
\[a\] and
\[bc\] so it is divisible by gcd(a, bc)

Answer 19

yes i think this is what you use. but this question requires some elementary algebra that i cannot do at this hor of the night

Answer 20

i think you have to use bezouty

Answer 21

joemath can finish it, because now you have to shake your bazouti

Answer 22

i need to go to bed

Answer 23

i just got here :( stay up!

Answer 24

me too! i am supposed to be doing work, but instead of working or sleeping i am here!

Answer 25

jk jk, im getting ready to sleep as well.

Answer 26

can u answer one more?

Answer 27

Prove the following statement. If k and L are coprime positive integers, then the linear Diophantine equation kx Ly = c has innitely many solutions in the positive integers.

Answer 28

do you mean kx+Ly=c?

Answer 29

kx-Ly=c and infinitly*

Answer 30

i have a solution for that on my computer. one sec...

Answer 31

night for reals joe
sorry i'm leaving you
and satellite

Answer 32

night :)

Answer 33

just switch s and t for k and L and that proof will work.

Answer 34

not sure about notation: x and y with bar over them?
negation?

Answer 35

im just denoting different integers from the x and y i used previously. you can call them something else if you like.

Answer 36

ok makes sense tyvm