Find coprime numbers less than n
Do you really need to print the answers to screen?

Most time consumed by the program is for printing each result to screen, using a simple counter or just saving all element in a list (should you need to work with the values, but not actually see them) saves a massive amount of time. Compare my results below:

With printing each value to console - your original code: 00:03:16.008651

static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            int n = 15600000;
            int j = n - 1;

            while (j &gt; 1)
            {
                if (GCD(n, j) == 1)
                    Console.WriteLine(j);

                j--;
            }
            sw.Stop();
            Console.WriteLine("Time elapsed: " + sw.Elapsed);
        } 


Adding value to list and then printing: 00:03:29.6715458 

static void Main(string[] args)
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    int n = 15600000;
    int j = n - 1;
    List&lt;int&gt; lst = new List&lt;int&gt;();

    while (j &gt; 1)
    {
        if (GCD(n, j) == 1)
            lst.Add(j);

        j--;
    }

    foreach(int ele in lst)
    {
        Console.WriteLine(ele);
    }

    sw.Stop();
    Console.WriteLine("Time elapsed: " + sw.Elapsed);
}


With counter or list (not printing to console): 00:00:04.5160762  

static void Main(string[] args)
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    int n = 15600000;
    int j = n - 1;
    int counter = 0;

    while (j &gt; 1)
    {
        if (GCD(n, j) == 1)
            counter++;

        j--;
    }
    sw.Stop();
    Console.WriteLine("Time elapsed: " + sw.Elapsed);
}