Use repeated squaring, where a2c ≡ (ac)2 (mod n) and a2c+1 ≡ a(ac)2 (mod n).…

Concept: Repeated squaring computes ab mod n by expressing b as a sum of powers of 2 and reducing after every multiplication.

For c ≥ 0, a2c ≡ (ac)2 (mod n), while a2c+1 ≡ a(ac)2 (mod n). These identities keep intermediate values small.

Application:

1. Write 17 = 16 + 1, so only 71 and 716 must be combined.

2. Square 7: 72 = 49, so 72 ≡ 49 (mod 561).

3. Square 49: 74 = 492 = 2401 = 4 × 561 + 157, so 74 ≡ 157 (mod 561).

4. Square 157: 78 ≡ 1572 = 24649 = 43 × 561 + 526, so 78 ≡ 526 (mod 561).

5. Square 526: 716 ≡ 5262 = 276676 = 493 × 561 + 103, so 716 ≡ 103 (mod 561).

6. Combine the powers: 717 ≡ 716 × 7 = 103 × 7 = 721 = 561 + 160, so 717 ≡ 160 (mod 561).

Cross-check: Because 561 = 3 × 11 × 17 and these factors are pairwise coprime, compare the result modulo each factor.

• Modulo 3: both 717 and 160 leave remainder 1.

• Modulo 11: 717 leaves remainder 6, and 160 also leaves remainder 6.

• Modulo 17: Fermat’s little theorem gives 716 ≡ 1, so 717 leaves remainder 7; 160 also leaves remainder 7.

The three residues agree, and the factors multiply to 561; therefore the unique result modulo 561 is 160.

Result: 717 mod 561 = 160.