Phương pháp qui nạp Toán học – Sai lầm ở đâu?

Sau đây tôi xin đăng lại nguyên văn bài đăng trên blog mathvn như sau:

Các học sinh 11 vừa học xong bài "Phương pháp quy nạp Toán học". Vậy các em hãy xem lời giải của bài toán sau đây.
Bài toán: Chứng minh rằng với mọi số nguyên dương n mệnh đề sau đây đúng: "Nếu a và b là những số nguyên dương mà max(a,b)=n thì a=b".
Lời giải:
Bước cơ sở: Với mỗi n nguyên dương, kí hiệu A(n) là mệnh đề đã cho. Rõ ràng A(1) đúng vì nếu max(a,b)=1 thì hiển nhiên a=b (do a,b nguyên dương).
Bước quy nạp: Giả sử A(k) đúng. Nếu a, b là những số nguyên dương sao cho max(a,b)=k+1 thì hai số c=a-1, d=b-1 có max(c,d)=k. Do đó theo giả thiết quy nạp, ta suy ra c=d. Vì vậy a-1=b-1, suy ra a=b. Vậy A(k+1) đúng.
Theo nguyên lý quy nạp, A(n) đúng với mọi số nguyên dương n.
Nếu bài toán trên đúng thì ta suy ra mọi số tự nhiên đều bằng nhau. Điều này là vô lí. Vì vậy chắc chắn trong lời giải trên có chỗ nào đó bị sai. Bạn hãy tìm xem!