1

I would like help solving this practice question. 

For a function f(x, y) defined below, what is the value of f(775, 527)? Here, x mod y represents the remainder after division of x by y.

f(x, y): if y = 0 then return x else return f(y, x mod y)


So it's saying x mod y represents 248?

Using the function definition, y does not equal 0 so that means I need to return f(y, x mod y).

775 mod 527 = 248

775 / 527 = 1 r248

f(527, 775 mod 527) -> f(527, 248) -> 527 mod 248 = 31

I was able to figure out the correct answer 31, however I don't see where it tells me 527, 248 should be solved as x mod y.

Edison
  • 131
  • 2
    This function is equivalent to $\gcd{(x,y)}$. It performs the Euclidean algorithm. – Peter Foreman Aug 07 '19 at 20:23
  • This is hard to follow. At no point is anyone claiming that " x mod y represents $248$". What would that even mean? – lulu Aug 07 '19 at 20:23
  • @Lulu It would mean 248 is congruent to x mod y. @ peter thanks. Could someone explain it? – Edison Aug 07 '19 at 20:28
  • Explain what? Obviously $775 \pmod {527}=248$, there's no mystery there is there? the function $f(x,y)$ is just $\gcd(x,y)$ except for degenerate cases. And $\gcd(775,527)=31$. But your post doesn't even refer to gcd...so I'm just not sure what you are asking. – lulu Aug 07 '19 at 20:57
  • What I'm saying is this. The function definition says return x else return f(y, x mod y). How did you know that f(y, x mod y) is the same as gcd(x,y) And how do you know that gcd(x,y) means the same as x (mod y)? Like how did we get from f(527, 248) to 527 mod 248? – Edison Aug 07 '19 at 21:02
  • 1
    Cf. Euclidean algorithm – J. W. Tanner Aug 07 '19 at 21:06
  • thank you guys. – Edison Aug 07 '19 at 21:07

0 Answers0