0

List common factors of integers

asked 2013-12-02 17:59:30 +0100

iGrasmat
1 ●1 ●1 ●1

updated 2013-12-02 20:58:00 +0100

kcrisman
12242 ●42 ●136 ●255

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 flag offensive close merge delete

Comments

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

kcrisman ( 2013-12-02 21:03:43 +0100 )edit

4 Answers

Sort by » oldest newest most voted

0

answered 2013-12-13 12:42:02 +0100

John Cremona
701 ●35 ●22

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.

edit flag offensive delete link

0

answered 2013-12-03 05:26:11 +0100

iGrasmat
1 ●1 ●1 ●1

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

edit flag offensive delete link

Comments

1

[factor(n) for n in L]

niles ( 2013-12-03 07:47:52 +0100 )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.

kcrisman ( 2013-12-03 09:17:01 +0100 )edit

0

answered 2013-12-02 21:07:21 +0100

kcrisman
12242 ●42 ●136 ●255

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.

edit flag offensive delete link

0

answered 2013-12-03 05:24:10 +0100

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

edit flag offensive delete link

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Question Tools

Stats

Asked: 2013-12-02 17:59:30 +0100

Seen: 1,875 times

Last updated: Dec 13 '13

Related questions

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.

Powered by Askbot version 0.7.59