# List common factors of integers

I have an N = pq, how do I list all common factors of 

• 153593241046674892978867376676801703195333499261944069748317 
• 595581987651106688365284842778515858399666547859870373300567 
• 456451496401875224148239517183071489325356803521953515331953 
• 732521324063413291774595255009269986704084399047286433357607 
• 697998237255232517803133139640937207091669333334886072165381 
• 665759389457622825753076124570026166878147870317677657070179 
• 1259985415634532155096901933248348760395037298806289273584121 
• 476063424836313254692044012215359579492944897779738635204933 
• 176294427788887166758409622538881387638478405478915857712513 
• 62438334806032841411208819703508997562716700552371135112697 
• 1155831644188436440125346091174944695123678746779608256372229 
• 592339248856319601455928821705423109007342115448431777433343

Also, how do I implement this in Sage? I've read something about the collect_common_factors() but I'm not sure how to use it.

edit retag close merge delete

Just FYI, collect_common_factors() is not relevant here - sorry. Do x.collect_common_factors? to see what it does.

( 2013-12-02 14:03:43 -0500 )edit

Sort by ยป oldest newest most voted

In this case, there don't seem to be any.

sage: L = [153593241046674892978867376676801703195333499261944069748317,595581987651106688365284842778515858399666547859870373300567,456451496401875224148239517183071489325356803521953515331953,732521324063413291774595255009269986704084399047286433357607,697998237255232517803133139640937207091669333334886072165381,665759389457622825753076124570026166878147870317677657070179,1259985415634532155096901933248348760395037298806289273584121,476063424836313254692044012215359579492944897779738635204933,176294427788887166758409622538881387638478405478915857712513,62438334806032841411208819703508997562716700552371135112697,1155831644188436440125346091174944695123678746779608256372229,592339248856319601455928821705423109007342115448431777433343]
sage: gcd(L)
1


In general, I guess you could do this?

sage: M = [22200,550, 6600,22300]
sage: gcd(M)
50
sage: divisors(gcd(M))
[1, 2, 5, 10, 25, 50]


Maybe I'm misunderstanding the question.

more

Thanks for your answer, but I mean common factor, not common divisor. For each intreger N, I need to know what all possible p*q pairs are.

For example, if I use factor(486152777213364595395443816492774905198988126405782351720339) I'll get 519667747617392375271433197553 * 935506926189494211870791066563

more

1

[factor(n) for n in L]

( 2013-12-03 00:47:52 -0500 )edit

I still don't understand the question. There aren't any common factors if there aren't any common divisors. Maybe you mean just that you want the factors of each number? Then @niles has the right answer. But "common" implies that the factors are "in common" among each other.

( 2013-12-03 02:17:01 -0500 )edit

I think the questioner means this: given a list of integers N each of the form N=p*q with p,q prime, he/she wants to find common factors of pairs of the Ns, so to take their GCDs in pairs. This works (after assigning your list of integers to the variable Ns):

sage: gcds = [GCD(N1,N2) for N1 in Ns for N2 in Ns if N1!=N2]
sage: [g for g in gcds if g>1]
[521192137187180935658403029827,
701397335649456892851007539749,
701397335649456892851007539749,
521192137187180935658403029827]


but there are certainly more efficient ways.

more

This post is a wiki. Anyone with karma >750 is welcome to improve it.

I do it in WINDOWS VIRBOX: L = [153593241046674892978867376676801703195333499261944069748317,595581987651106688365284842778515858399666547859870373300567,456451496401875224148239517183071489325356803521953515331953,732521324063413291774595255009269986704084399047286433357607,697998237255232517803133139640937207091669333334886072165381,665759389457622825753076124570026166878147870317677657070179,1259985415634532155096901933248348760395037298806289273584121,476063424836313254692044012215359579492944897779738635204933,176294427788887166758409622538881387638478405478915857712513,62438334806032841411208819703508997562716700552371135112697,1155831644188436440125346091174944695123678746779608256372229,592339248856319601455928821705423109007342115448431777433343];L

[153593241046674892978867376676801703195333499261944069748317, 595581987651106688365284842778515858399666547859870373300567, 456451496401875224148239517183071489325356803521953515331953, 732521324063413291774595255009269986704084399047286433357607, 697998237255232517803133139640937207091669333334886072165381, 665759389457622825753076124570026166878147870317677657070179, 1259985415634532155096901933248348760395037298806289273584121, 476063424836313254692044012215359579492944897779738635204933, 176294427788887166758409622538881387638478405478915857712513, 62438334806032841411208819703508997562716700552371135112697, 1155831644188436440125346091174944695123678746779608256372229, 592339248856319601455928821705423109007342115448431777433343] gcd(L)

1

more