using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace labacrpt
{
    class Program
    {
        static void Main(string[] args)
        {
            int m, a;
            while (true)
            {
                Console.Write("n=");
                m = Convert.ToInt32(Console.ReadLine());
                Console.Write("a=");
                a = Convert.ToInt32(Console.ReadLine());
                int[] m1 = new int[] { a, 1, 0 };
                int[] m2 = new int[] { m, 0, 1 };
                int[] x = new int[3];
                if (a > 0 && m > 1)
                {
                    while (true)
                    {
                        x[0] = m1[0] - m2[0] * (m1[0] / m2[0]);
                        x[1] = m1[1] - m2[1] * (m1[0] / m2[0]);
                        x[2] = m1[2] - m2[2] * (m1[0] / m2[0]);
                        //for (int i = 0; i < 3; i++)
                        //    Console.Write(x[i] + " ");
                        //Console.WriteLine();
                        m1[0] = m2[0];
                        m1[1] = m2[1];
                        m1[2] = m2[2];
                        m2[0] = x[0];
                        m2[1] = x[1];
                        m2[2] = x[1];
                        if (m2[0] == 0) break;
                    }
                    if (m1[0] == 1)
                    {
                        Console.Write("Result=");
                        if (m1[1] < 0)
                            m1[1] = m1[1] + m;
                        Console.WriteLine(m1[1]);
                    }
                    else Console.WriteLine("Числа не взаимнопростые");
                }
                else Console.WriteLine("Некорректные элементы");
                Console.WriteLine("_________________________________________");
            }
        }
    }
}