Solveeit Logo
Login

Question

Question: Let a function f : N → N be defined $f(m,n)= \begin{cases} f(m-n, n); \text{ if } m \geq n \\ m; \t...

Let a function f : N → N be defined

f(m,n)={f(m−n,n); if m≥nm; if m<nf(m,n)= \begin{cases} f(m-n, n); \text{ if } m \geq n \\ m; \text{ if } m < n \end{cases}

A

f(22024,2251−1)f(2^{2024}, 2^{251}-1)

B

f(22023,2252−1)f(2^{2023}, 2^{252}-1)

C

f(22024,2253−1)f(2^{2024}, 2^{253}-1)

D

f(22016,2252−1)f(2^{2016}, 2^{252}-1)

Answer

(P) → (3), (Q) → (4), (R) → (1), (S) → (1)

Explanation

Solution

The function f(m,n)f(m, n) is equivalent to mmod  nm \mod n.

  • (P) f(22024,2251−1)=216f(2^{2024}, 2^{251} - 1) = 2^{16} because 22024≡216(mod2251−1)2^{2024} \equiv 2^{16} \pmod{2^{251} - 1}.
  • (Q) f(22023,2252−1)=27f(2^{2023}, 2^{252} - 1) = 2^7 because 22023≡27(mod2252−1)2^{2023} \equiv 2^7 \pmod{2^{252} - 1}.
  • (R) f(22024,2253−1)=1f(2^{2024}, 2^{253} - 1) = 1 because 22024≡1(mod2253−1)2^{2024} \equiv 1 \pmod{2^{253} - 1}.
  • (S) f(22016,2252−1)=1f(2^{2016}, 2^{252} - 1) = 1 because 22016≡1(mod2252−1)2^{2016} \equiv 1 \pmod{2^{252} - 1}.

Therefore, the correct matches are:

  • (P) → (3)
  • (Q) → (4)
  • (R) → (1)
  • (S) → (1)