3. Докажите, что числа: а) 66 и 85 взаимно простые; б) 30 и 58 не взаимно простые.

а) Разложим числа на простые множители: 66 = 2 · 3 · 11, 85 = 5 · 17. Общих простых множителей нет, поэтому НОД(66, 85) = 1. Следовательно, числа взаимно простые.

б) Разложим числа на простые множители: 30 = 2 · 3 · 5, 58 = 2 · 29. Общий простой множитель — 2, поэтому НОД(30, 58) = 2. Следовательно, числа не являются взаимно простыми.