Exercise 1: The Multiply-vs-Factor Ratio for 101 and 103 — Possible Solution ==================================================================== GIVEN ------------------------------ p = 101, q = 103, product = 101 x 103 = 10,403 STEP 1: TRIAL DIVISIONS TO VERIFY 101 IS PRIME ------------------------------ sqrt(101) is approximately 10.05, so trial division only needs to check candidate divisors 2 through 10. Testing i = 2,3,4,5,6,7,8,9,10 - none divide 101 evenly. That's 9 trial divisions to confirm 101 is prime. STEP 2: TRIAL DIVISIONS TO FACTOR 10,403 FROM SCRATCH ------------------------------ sqrt(10403) is exactly 101 (since 101 x 103 = 10403 and 101 is the SMALLER of the two factors, it sits almost exactly at the square root boundary). Testing i = 2 through 100 - none of these divide 10403 evenly (that's 99 failed trial divisions). Testing i = 101 - THIS divides 10403 evenly (10403 / 101 = 103), so the factor is found here. Total trial divisions needed: 100 (99 failures plus the one that succeeds at i=101). STEP 3: THE RATIO ------------------------------ 100 / 9 = 11.11 (approximately) RESULT ------------------------------ Factoring the product from scratch takes roughly 11.1x more trial divisions than verifying just one of its prime factors alone - even at this tiny four-digit scale. This happens because verifying a single number's primality only needs to search up to its OWN square root, while factoring a product with no prior knowledge needs to search up to the square root of the much larger product itself. WHY THIS WORKS AS AN ANSWER ------------------------------ Both trial-division counts are computed precisely rather than estimated, correctly identifying that 10403's smaller factor (101) sits almost exactly at its own square root boundary - meaning the full search range up to that point genuinely has to be exhausted before the factor is found, matching this chapter's own worked demonstration of the same asymmetry at a slightly different scale.