Hi, I'm new here, so please bear with me.

I'm going through "The Art and Craft of Problem Solving" by Paul Zeitz (disclaimer: I'm a high school student who's self studying. I don't know if this is the right subforum), and I got (really) stuck at letter d.

All I've got is that:

The maximum value of the GCD is a, which means that x=1 and y=0, and that in all other cases either x or y has to be negative, and the other positive.

I tried fiddling with some algebra. For the case that x is the negative number,

since b = qa + r,

ax + by = ax + y(qa + r)
= ax + aqy + ry
= a(x + qy) + ry,

which means that |x| >= qy, but not to the point that a(x + qy) + ry is 0 or negative.

Aand that's it. I feel like I'm missing something obvious and I'm digging in the wrong direction.

Maybe a push in the right direction? I still want to figure it out by myself

Envoyé de mon SM-J730G en utilisant Tapatalk