/sci/ - Science & Math » Thread #14126047

266KiB, 756x447, collapse.png

View Same Google iqdb SauceNAO

Anonymous Thu 20 Jan 00:46:22 2022 No.14126047 View Reply Original Report

Quoted By: >>14126083 >>14126084 >>14126177 >>14126248 >>14126326 >>14128226 >>14129274

I'm trying to prove the following. Given d=gcd(a,b), with positive integers a, b, since d|a, a=dh for some h in the integers. If a|bc, then h|c.

How to go about this? I tried by cases (a|b and a doesnt divide b), I tried giving a and b as a product of prime factors and doing some algebra, but so far I keep hitting roadblocks. Help?

Anonymous

Anonymous Thu 20 Jan 2022 00:59:40 No.14126083 Report

Quoted By: >>14126091

>>14126047
h has no factors in common with b. you can see this because if it did those factors would be in d(the gcd) ergo h divides c

Anonymous

Anonymous Thu 20 Jan 2022 01:00:10 No.14126084 Report

Quoted By:

>>14126047
For cases, I've tried the following

Case 1: Let a|b. Because a|a and a|b, a is a common divisor of a and b. Since d is the greatest common divisor, a<=d. But we are given that d|a, so d<=a. Thus d=a, so the equation a=dh implies h=1, then trivially h|c.

Case 2: Let a not divide b. Because we are not given (a,b)=1, we can't apply Euclid's Lemma, so I'm kinda stumped here

Anonymous

Anonymous Thu 20 Jan 2022 01:02:21 No.14126091 Report

Quoted By: >>14126139

>>14126083
This is not necessarily true

Consider a=2^2 * 3^2, b=2^2 * 3 * 7.
Then d=2^2*3, so h=3. But both b and h have a 3, so h may divide b

Anonymous

Anonymous Thu 20 Jan 2022 01:17:21 No.14126139 Report

Quoted By:

>>14126091
thats true but if h is a factor of a(implied by a=dh) and it could also divide b given the factors already in the gcd then it would be part of d. since its not included in d then if it were multiplied with d, d wouldnt divide b. this implies that h couldnt also divide b after d has which forces it to divide h

Anonymous

Anonymous Thu 20 Jan 2022 01:20:03 No.14126144 Report

Quoted By: >>14126168

Anonymous

Anonymous Thu 20 Jan 2022 01:27:11 No.14126168 Report

Quoted By: >>14126254

>>14126144
cant use euclids lemma here and k is superfluous; just do p|h and p|b to get your contradiction

Anonymous

Anonymous Thu 20 Jan 2022 01:31:06 No.14126177 Report

Quoted By:

>>14126047
Suppose that a|bc then there is an integer k with
ak = bc

d=gcd(a,b) so there are integers x,y with
ax + by = d

Now multiply it by hk and simplify:
axhk + byhk = dhk
bchx + bhky = bc
chx + hky = c
h(cx + ky) = c

Anonymous

Anonymous Thu 20 Jan 2022 01:51:47 No.14126248 Report

Quoted By:

>>14126047
h is exactly all the prime factors of a not in b. a divides bc so bc contains all the prime factors of a. bc contains exactly the prime factors of b and c. So c must contain the prime factors of a not in b, which is h. That is, h|c.

Anonymous

Anonymous Thu 20 Jan 2022 01:53:38 No.14126254 Report

Quoted By:

>>14126168
This is true about Euclid's Lemma, but we do have a separate proposition given to us that if a|bc, and (a,b)=1, then a|c. Since (h,k)=1, this should apply here, no? Like if I swap this out then my proof stands?

Anonymous

Anonymous Thu 20 Jan 2022 02:11:43 No.14126326 Report

Quoted By: >>14126352

>>14126047
let d = gcd(a,b). then, a = dk for some k.
suppose a|bc.
then, k|c.
a | bc => bc = am for some m
use extended euclidean algorithm to get that
ax + by = d for some x,y. continue multiplying both by c
acx + bc = dc, replace bc by am,
acx + am = dc, replace a by dk
dkcx + dkm = dc, divide both sides by d
kcx + km = c, factor out k
k(cx + m) = c
i.e. c is a multiple of k. QED.

Anonymous

Anonymous Thu 20 Jan 2022 02:20:11 No.14126352 Report

Quoted By:

>>14126326
What happened to the y?

Anonymous

Anonymous Thu 20 Jan 2022 15:14:31 No.14128226 Report

Quoted By:

>>14126047
a | bc
dh | dkc
h | kc
gcd(h,k) = 1 by construction of d
h | c

Anonymous

Anonymous Thu 20 Jan 2022 21:00:51 No.14129274 Report

Quoted By:

>>14126047
>I tried giving a and b as a product of prime factors and doing some algebra, but so far I keep hitting roadblocks
A lot of solutions already but I'll show you how you could have done it with product of prime factors (the algebraic way, not by treating every prime number separately which would be easier)

Let $p_i$ be $i$ -th prime number.
Suppose that $p_m$ is the biggest prime factor between $A$ and $B$ .
Then
$A = p_1^{a_1}\cdotp_2^{a_2}\dots p_m^{a_m} \\ B = p_1^{b_1}\cdotp_2^{b_2}\dots p_m^{b_m}$
Then if $D = \text{gcd}(A, B)$
$D = p_1^{d_1}\cdot p_2^{d_2}\dots p_m^{d_m} \\ d_i = \text{min}\{a_i, b_i\}$
and if $A = D\cdot H$ then $a_i = d_i + h_i$ .
Considering $C$
$C = p_1^{c_1}\cdotp_2^{c_2}\dots p_m^{c_m} \\ <br />\implies B\cdot C = p_1^{b_1+c_1}\cdot p_2^{b_2+c_2}\dots p_m^{b_m+c_m}$
now $A|B\cdot C \implies a_i \leq b_i + c_i$ .
If $d_i = a_i \iff d_i = d_i + h_i \implies h_i = 0$ and obviously $h_i = 0 \leq c_i$ .
Else $d_i = b_i$ so $a_i \leq b_i + c_i \iff d_i + h_i \leq c_i + b_i \iff h_i \leq c_i$
So for all $i$ : $h_i \leq c_i$ , i.e $H | C$ .

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches