Пошаговое объяснение:
Покажем, что при любых натуральных m и n числа 3m+5n+1 и 5m+9n+2 имеют разную чётность. Для этого вычтем из одного другое.
5m+9n+2-3m-5n-1=2m+4n+1=2(m+2n)+1 - нечётное число. Но как известно разность чисел одинаковой чётности - чётное число, а разной чётности - нечётное. Значит, числа 3m+5n+1 и 5m+9n+2 имеют разную чётность, то есть при любых m и n среди них будет одно чётное число. Но тогда в его разложении на простые множители содержится 2, которая при возведении в степень (6 или 7, в зависимости какое число оказалось чётным) даст множитель 64 или 128. Из чего следует, что число 
будет делиться на 64, то есть будет делиться на 