Để tìm tất cả các cặp số tự nhiên a, b thỏa mãn điều kiện a + b = 135 và ƯCLN(a, b) ≤ 15, ta có thể thực hiện các bước sau:

1. Vì a và b là hai số tự nhiên và a + b = 135, nên ta có thể thử tất cả các giá trị của a từ 1 đến 134 và tính giá trị tương ứng của b.

2. Sau đó, kiểm tra xem ƯCLN(a, b) có lớn hơn 15 hay không. Nếu không, ta sẽ lưu lại cặp số a, b đó.

3. Cuối cùng, liệt kê tất cả các cặp số a, b mà ta đã tìm được.

Dưới đây là một đoạn mã Python thực hiện việc này:

```python
def UCLN(a, b):
while b != 0:
a, b = b, a % b
return a

pairs = []
for a in range(1, 135):
b = 135 - a
if UCLN(a, b) <= 15:
pairs.append((a, b))

print("Các cặp số tự nhiên a, b thỏa mãn điều kiện a + b = 135 và ƯCLN(a, b) ≤ 15 là:")
for pair in pairs:
print(pair)
```

Kết quả khi chạy đoạn mã trên sẽ là tất cả các cặp số a, b thỏa mãn yêu cầu đề bài.