Linear Congruences

Submit

Your name:
File:
Open code-statistics:

Language is selected by the extension of the file. See the list of supported languages to know the extension of your language.

Problem

Solve systems of linear congruences (modular equations).
Note: Not all are solvable using the Chinese Remainder Theorem, and some aren't solvable at all!

http://mathworld.wolfram.com/LinearCongruenceEquation.html
http://en.wikipedia.org/wiki/Chinese_Remainder_Theorem
http://en.wikipedia.org/wiki/Method_of_successive_substitution

Options

exec is denied

now post-mortem time, all source codes will be revealed

Sample input:_

x = 3 (mod 4)

x = 4 (mod 3)

x = 1 (mod 2)
x = 2 (mod 3)
x = 3 (mod 4)
x = 4 (mod 5)
x = 5 (mod 6)
x = 0 (mod 7)

x = 2 (mod 3)
x = 3 (mod 5)
x = 2 (mod 7)

Sample output:

3 + 4k
no solutions
119 + 420k
23 + 105k

Sample input:_

x = 0 (mod 3)
x = 2 (mod 10)

x = 0 (mod 5)
x = 3 (mod 10)

x = 0 (mod 7)
x = 5 (mod 10)

x = 0 (mod 11)
x = 7 (mod 10)

x = 0 (mod 13)
x = 11 (mod 100)

x = 0 (mod 17)
x = 13 (mod 100)

x = 0 (mod 19)
x = 17 (mod 100)

x = 0 (mod 23)
x = 19 (mod 100)

x = 0 (mod 29)
x = 23 (mod 100)

x = 0 (mod 31)
x = 29 (mod 100)

x = 0 (mod 37)
x = 31 (mod 100)

x = 0 (mod 41)
x = 37 (mod 100)

x = 0 (mod 43)
x = 41 (mod 100)

x = 0 (mod 47)
x = 43 (mod 100)

x = 0 (mod 53)
x = 47 (mod 100)

x = 0 (mod 59)
x = 53 (mod 100)

x = 0 (mod 61)
x = 59 (mod 100)

x = 0 (mod 67)
x = 61 (mod 100)

x = 0 (mod 71)
x = 67 (mod 100)

x = 0 (mod 73)
x = 71 (mod 100)

x = 0 (mod 79)
x = 73 (mod 100)

x = 0 (mod 83)
x = 79 (mod 100)

x = 0 (mod 89)
x = 83 (mod 100)

x = 0 (mod 97)
x = 89 (mod 100)

Sample output:

12 + 30k
no solutions
35 + 70k
77 + 110k
611 + 1300k
1513 + 1700k
817 + 1900k
1219 + 2300k
2523 + 2900k
1829 + 3100k
2331 + 3700k
2337 + 4100k
3741 + 4300k
3243 + 4700k
5247 + 5300k
3953 + 5900k
1159 + 6100k
5561 + 6700k
5467 + 7100k
1971 + 7300k
6873 + 7900k
1079 + 8300k
4183 + 8900k
3589 + 9700k

Sample input:_

x = 3 (mod 5)
x = 5 (mod 8)

x = 5 (mod 8)
x = 3 (mod 4)

x = 3 (mod 4)
x = 2 (mod 7)
x = 1 (mod 9)

x = 0 (mod 2)
x = 0 (mod 3)
x = 0 (mod 5)
x = 0 (mod 7)
x = 0 (mod 11)

x = 1 (mod 2)
x = 1 (mod 3)
x = 1 (mod 5)
x = 1 (mod 7)
x = 1 (mod 11)

x = 1 (mod 2)
x = 2 (mod 3)
x = 3 (mod 5)
x = 4 (mod 7)
x = 5 (mod 11)

x = 1 (mod 2)
x = 2 (mod 3)
x = 4 (mod 5)
x = 6 (mod 7)
x = 10 (mod 11)

x = 2 (mod 2)
x = 4 (mod 3)
x = 6 (mod 5)
x = 8 (mod 7)
x = 10 (mod 11)

x = 34 (mod 49)
x = 9 (mod 90)
x = 9 (mod 90)
x = 66 (mod 71)
x = 0 (mod 3)

x = 44 (mod 85)
x = 76 (mod 81)
x = 4 (mod 16)
x = 38 (mod 98)
x = 4 (mod 16)
x = 59 (mod 95)
x = 31 (mod 33)

x = 35 (mod 87)
x = 31 (mod 32)
x = 31 (mod 88)
x = 11 (mod 93)
x = 8 (mod 15)
x = 5 (mod 6)
x = 6 (mod 29)
x = 40 (mod 49)
x = 35 (mod 87)

x = 34 (mod 63)
x = 7 (mod 9)
x = 9 (mod 34)
x = 13 (mod 42)
x = 13 (mod 28)
x = 49 (mod 100)

x = 10 (mod 27)
x = 37 (mod 96)
x = 16 (mod 59)

x = 7 (mod 49)
x = 1 (mod 31)
x = 17 (mod 24)
x = 24 (mod 43)
x = 24 (mod 43)

x = 1 (mod 4)
x = 1 (mod 44)
x = 5 (mod 36)
x = 5 (mod 68)
x = 5 (mod 9)

x = 10 (mod 15)
x = 76 (mod 78)
x = 4 (mod 24)
x = 14 (mod 49)
x = 0 (mod 10)
x = 68 (mod 79)
x = 42 (mod 94)
x = 14 (mod 49)

x = 36 (mod 45)
x = 53 (mod 61)
x = 6 (mod 7)
x = 6 (mod 60)
x = 14 (mod 64)
x = 54 (mod 72)
x = 9 (mod 31)

x = 20 (mod 94)
x = 4 (mod 54)
x = 20 (mod 47)
x = 20 (mod 94)

x = 9 (mod 10)
x = 1 (mod 3)
x = 13 (mod 39)
x = 19 (mod 31)
x = 29 (mod 40)
x = 3 (mod 86)
x = 53 (mod 64)
x = 3 (mod 86)

x = 76 (mod 86)
x = 20 (mod 27)
x = 16 (mod 49)
x = 10 (mod 16)
x = 71 (mod 87)
x = 2 (mod 84)

x = 37 (mod 43)
x = 80 (mod 86)
x = 4 (mod 8)
x = 15 (mod 79)
x = 72 (mod 90)
x = 15 (mod 79)

x = 5 (mod 32)
x = 5 (mod 54)
x = 5 (mod 18)

x = 9 (mod 41)
x = 43 (mod 88)
x = 89 (mod 94)
x = 43 (mod 88)
x = 43 (mod 44)
x = 27 (mod 36)
x = 33 (mod 34)

x = 49 (mod 94)

x = 1 (mod 2)
x = 75 (mod 90)
x = 48 (mod 53)
x = 3 (mod 87)
x = 19 (mod 22)
x = 19 (mod 23)

x = 13 (mod 40)
x = 13 (mod 15)
x = 43 (mod 69)
x = 13 (mod 36)

x = 10 (mod 63)
x = 10 (mod 63)
x = 2 (mod 29)
x = 30 (mod 61)
x = 3 (mod 49)
x = 50 (mod 59)
x = 10 (mod 70)

x = 75 (mod 93)
x = 24 (mod 26)
x = 12 (mod 21)
x = 6 (mod 60)
x = 12 (mod 42)
x = 33 (mod 63)
x = 62 (mod 83)

x = 18 (mod 55)
x = 1 (mod 39)
x = 37 (mod 41)
x = 28 (mod 29)
x = 5 (mod 19)
x = 18 (mod 44)

x = 19 (mod 63)
x = 10 (mod 36)
x = 19 (mod 27)
x = 33 (mod 79)

x = 8 (mod 12)
x = 26 (mod 30)
x = 0 (mod 2)
x = 18 (mod 79)
x = 54 (mod 61)
x = 34 (mod 71)
x = 8 (mod 28)
x = 41 (mod 45)

x = 1 (mod 3)
x = 34 (mod 63)
x = 22 (mod 66)
x = 90 (mod 98)
x = 6 (mod 35)
x = 13 (mod 21)

x = 49 (mod 56)
x = 65 (mod 82)
x = 25 (mod 87)
x = 7 (mod 21)
x = 1 (mod 45)
x = 1 (mod 2)

x = 24 (mod 25)
x = 0 (mod 14)
x = 34 (mod 38)
x = 0 (mod 28)
x = 4 (mod 5)
x = 4 (mod 10)

x = 10 (mod 30)
x = 4 (mod 18)
x = 0 (mod 35)
x = 0 (mod 7)
x = 25 (mod 31)

x = 12 (mod 21)
x = 0 (mod 6)
x = 12 (mod 35)
x = 12 (mod 38)
x = 12 (mod 31)
x = 12 (mod 14)

x = 3 (mod 4)
x = 15 (mod 29)
x = 1 (mod 2)
x = 3 (mod 6)
x = 22 (mod 31)

x = 16 (mod 40)
x = 0 (mod 8)
x = 21 (mod 35)

Sample output:

13 + 40k
no solutions
163 + 252k
0 + 2310k
1 + 2310k
1523 + 2310k
2309 + 2310k
no solutions
279 + 313110k
724 + 1128148560k
383 + 232589280k
349 + 107100k
901 + 50976k
497 + 1567608k
617 + 6732k
700 + 283821720k
846 + 38122560k
490 + 2538k
949 + 16635840k
506 + 26396496k
252 + 1222920k
5 + 864k
747 + 25945128k
49 + 94k
525 + 34997490k
733 + 8280k
640 + 460276110k
726 + 42145740k
898 + 193830780k
586 + 59724k
176 + 431107740k
286 + 48510k
721 + 2996280k
224 + 13300k
490 + 19530k
12 + 123690k
363 + 10788k
56 + 280k

Ranking

Ruby _

RankUserSizeTimeDateStatistics
1kaki2530.22372009/06/24 16:27:060B / 114B / 131B
2kaki2460.48092009/07/10 01:55:430B / 106B / 133B

Perl _

RankUserSizeTimeDateStatistics
1tybalt891030.52132009/06/24 17:36:520B / ?B / ?B
2mitch schwartz1000.14932013/01/03 01:59:200B / ?B / ?B
3mitchs (tybalt89) (namefix)1000.07422014/02/14 12:27:580B / 32B / 62B

Python _

RankUserSizeTimeDateStatistics
1hallvabo2261.28802009/06/24 08:21:270B / 120B / 76B
2lifthrasiir2270.26282009/06/12 23:39:420B / 118B / 88B
3tryeng2410.92842009/05/28 01:22:500B / 131B / 70B

Common LISP _

RankUserSizeTimeDateStatistics
1kozima2541.44532009/06/24 13:30:400B / 149B / 82B
2kozima2521.60782009/06/25 09:05:510B / 148B / 82B

JavaScript _

RankUserSizeTimeDateStatistics
1nn2310.48682009/05/30 17:43:380B / 106B / 120B
2murky-satyr2130.13362009/11/29 22:30:530B / 100B / 108B

J _

RankUserSizeTimeDateStatistics
1I., S.1140.13502012/08/06 20:59:380B / 28B / 81B

C _

RankUserSizeTimeDateStatistics
151b1890.06732009/06/22 00:16:050B / 98B / 87B
2ozy4dm1900.14422009/06/17 14:18:150B / 94B / 92B
3funnything1970.02952009/06/21 07:46:080B / 93B / 99B
4pi80273420.04042009/05/29 10:14:280B / 186B / 136B
551b1790.02292009/06/27 21:49:220B / 88B / 87B

D _

RankUserSizeTimeDateStatistics
151b2160.04712009/06/28 21:23:170B / 110B / 96B

Haskell _

RankUserSizeTimeDateStatistics
1notogawa1800.16822009/06/11 23:34:080B / ?B / ?B
2moriA1880.19842009/06/19 00:26:010B / 100B / 71B

AWK _

RankUserSizeTimeDateStatistics
1nn1760.19142009/05/30 20:15:050B / 78B / 90B

Postscript _

RankUserSizeTimeDateStatistics
1yshl(bin)1971.42692009/06/06 20:24:0382B / 68B / 43B
2yshl3351.47702009/06/06 20:23:360B / 239B / 47B

Groovy _

RankUserSizeTimeDateStatistics
1murky-satyr2493.84562009/11/29 22:17:470B / 119B / 120B
2nn2748.22932009/11/07 00:33:560B / 142B / 120B

Language Ranking_

RankLangUserSizeScore
1Perlmitchs (tybalt89) (namefix)10010000
2JI., S.1148771
3AWKnn1765681
4C51b1795586
5Haskellnotogawa1805555
6Postscriptyshl(bin)1975076
7JavaScriptmurky-satyr2134694
8D51b2164629
9Pythonhallvabo2264424
10Rubykaki2464065
11Groovymurky-satyr2494016
12Common LISPkozima2523968

return top