title: Finding numbers with given GCD values
body: <p>I was looking over the Eucledian algorithm for finding GCD of numbers. Now, it can be used to find GCD of two given numbers. However, if I am given GCD of a single number with multiple other numbers, for example, GCD of the first number with 3 other numbers (including itself), that is, </p>
  
  <p>Given is: GCD of a with a, GCD of a with b, GCD of a with c, GCD of a with d. 
  and same goes for the other numbers, i.e. GCD of b with a, b with b, .....</p>
  
  <p>Then, how can I find the individual numbers? I know that GCD(a,a) = a itself but the problem here is, that the individual GCD given are in a random order, and therefore, I don't know which input number is the GCD of which two numbers. In that case, how do I find the individual numbers? </p>
  
  <p>Here is my GCD code: </p>
  
  <pre><code>int gcd(int a,int b)
  {
     if(b==0)
     {
         return a;
     }
     return gcd(b,a%b);
  }
  </code></pre>
  
  <p>Example: Let's say the input given is,</p>
  
  <pre><code>3 1 3 1 4 2 2 3 6
  3 //(total numbers we have to find in original array)
  </code></pre>
  
  <p>Then output should be, 3 4 6. Because if you calculate GCD pairwise (total 9 pairs and hence 9 numbers as input) of each of these numbers, then we get the output as above. </p>
  
  <pre><code>Explanation: 3 -&gt; GCD of (3,3)
  1 -&gt; GCD of (3,4)
  3 -&gt; GCD of (3,6)
  1 -&gt; GCD of (4,3)
  4 -&gt; GCD of (4,4)
  2 -&gt; GCD of (4,6)
  6 -&gt; GCD of (6,6)
  3 -&gt; GCD of (6,3)
  2 -&gt; GCD of (6,4)
  </code></pre>
  
  <p>Therefore, I have to find the numbers whose GCD is given as input. Hence, (3,4,6) are those numbers. </p>