Consider a software for loop of the form Body of Loop; } , Where a is a non-nega
ID: 2900980 • Letter: C
Question
Consider a software for loop of the form
Body of Loop;
} ,
Where a is a non-negative integer and b and c positive integers. Consider the
question of whether this loop will ever terminate. This question isn't as trivial
as you might think, since computer arithmetic is performed modulo M for some
large integer M (e.g., M = 2^32 ). Thus i takes the values a, a + c, a + 2c, . . . .,
where each term in the sequence is reduced modulo M . The value of i might
miss b the rst time through the loop as it increases towards M , but then hit b
later after it cycles around a few times.
As an example, consider the case where a = 3, b = 7, c = 6,M = 16. Then i
takes on the successive values 3, 9, 15, 5, 11, 1, 7.
In fact, the loop terminates if and only if
d| (b - a );
where d = gcd (M, c ).
Prove if the loop terminates, then d| (b - a ).
Explanation / Answer
if the loop terminates , then
b = a+nc - kM,
assuming we added c n times and it crossed largest integer M k times
=>
b-a = nc-kM
let d = gcd (M,c)
=>
d|M => d|kM
d|c => d|nc
=>
d|(nc-kM)
=>d|(b-a)
thus proved