A Formula for Congruences The Chinese Remainder Theorem can be quite useful in modular arithmetic.

For example, consider the following set of congruence relations:



For sets of congruence relations like this, where all the bases (3, 5, 7 in this example) are co-prime with each other, there will be one and only one integer n between 1 and the product of the bases (3*5*7 = 105 in this example) inclusive that satisfies the relations.

In this example, the number would be 14, generated by this formula:



where 2, 4, and 0 are given from the above example.

70, 21, 15 are the coefficients of the formula and they are dependent on the bases, 3, 5, 7.

To calculate the coefficients of the formula (70, 21, 15 in our example) for a set of bases, we use the following procedure.

For each number a in a set of bases:


Find the product of all of the other bases, denoted as P.
Find the first multiple of P that leaves a remainder of 1 when divided by a. This is the coefficient of a.


For example, to calculate the coefficient that corresponds to the base 3, we find the product of all the other bases (i.e. 5*7 = 35) and then find the first multiple of that product that leaves a remainder of 1 when divided by the base.

In this case, 35 leaves a remainder of 2 when divided by 3, but 35*2 = 70 leaves a remainder of 1 when divided by 3, so 70 is the corresponding coefficient for 3. Similarly, 3*7 = 21 leaves a remainder of 1 when divided by 5 and 3*5 = 15 leaves a remainder of 1 when divided by 7.

In a nutshell

For each number a in a set of numbers:


Find the product of all of the other numbers, denoted as P.
Find the first multiple of P that leaves a remainder of 1 when divided by a. This is the coefficient of a.


The challenge


The challenge is, for a set of two or more bases, to find the set of corresponding coefficients.
The set of bases are guaranteed to be pairwise co-prime and each base is guaranteed to be larger than 1.
Your input is a list of integers as input [3,4,5] or space-separated string "3 4 5" or however your inputs work.
Your output should either be a list of integers or space-separated string that denotes the set of coefficients.


Test cases

input             output
[3,5,7]           [70,21,15]
[2,3,5]           [15,10,6]
[3,4,5]           [40,45,36]
[3,4]             [4,9]
[2,3,5,7]         [105,70,126,120]
[40,27,11]        [9801,7480,6480]
[100,27,31]       [61101,49600,56700]
[16,27,25,49,11]  [363825,2371600,2794176,5583600,529200]


Many thanks to Leaky Nun for his help in writing this challenge. As always, if the problem is unclear, please let me know. Good luck and good golfing!
Haskell, 61 55 53 bytes

f x=[[p|p&lt;-[0,product x`div`n..],p`mod`n==1]!!0|n&lt;-x]


Defines a function f that takes input and gives output as a list of integers.

f x=[                                          |n&lt;-x]  (1)
              product x                                (2)
                       `div`n                          (3)


First we loop over all integers in the input (1). Then we take the product of all of the integers (2) and divide by n to get just the product of the non-n integers, which is P (3).

           [0,               ..]                       (4)
     [p|p&lt;-                     ,p`mod`n==1]           (5)
                                            !!0        (6)


Then we use the result (P) as the step value for a range starting at zero (4). We take the result, [0, P, 2P, 3P, ...], and filter it on values for which the result of a mod-n operation is one (5). Finally, we take the first element, which works thanks to lazy evaluation (6).

Thanks to @xnor for 2 bytes!