Kiểm Tra Cặp Mã Bảo Mật Vietcombank

Mô tả

Hệ thống Mobile Banking của Vietcombank cần sinh cặp mã khóa bảo mật ngẫu nhiên để mã hóa giao dịch. Một cặp mã được xem là hợp lệ khi hai số nguyên dương đó nguyên tố cùng nhau, tức là ước chung lớn nhất của chúng bằng 1.

Bài toán này lấy cảm hứng từ ý tưởng của bộ xử lý Rekursiv (Scotland, 1988) — nơi tiên phong tích hợp cơ chế bảo mật bộ nhớ ngay tại phần cứng. Dù sản phẩm gốc không thành công về mặt thương mại, triết lý bảo mật cốt lõi đã sống sót qua nhiều thế hệ công nghệ. Ngày nay, lớp trừu tượng an toàn được đặt vào phần mềm — và kiểm tra nguyên tố cùng nhau chính là một mắt xích nhỏ nhưng quan trọng trong luồng sinh mã.

Nhiệm vụ của bạn: cho trước hai số nguyên dương $a$ và $b$, hãy xác định chúng có phải là một cặp nguyên tố cùng nhau hay không. Trả về true nếu có, false nếu không.

Đầu vào

Hai số nguyên dương $a$ và $b$, phân tách bằng dấu phẩy.

Đầu ra

• Trả về true nếu $\gcd(a, b) = 1$ (hai số nguyên tố cùng nhau).
• Trả về false nếu ngược lại.

Ràng buộc

• $1 \le a, b \le 10^9$

Ví dụ

Ví dụ 1:

Đầu vào: 14, 15

Đầu ra: true

Giải thích: Ước số của 14 là {1, 2, 7, 14}, ước số của 15 là {1, 3, 5, 15}. Ước chung lớn nhất là 1, nên hai số này nguyên tố cùng nhau.

Ví dụ 2:

Đầu vào: 14, 21

Đầu ra: false

Giải thích: Cả 14 và 21 đều chia hết cho 7. Ước chung lớn nhất là 7, khác 1, nên không nguyên tố cùng nhau.