Functional Equation on Natural Numbers

CAT 2024 Slot 2 · QA · Hard · Functions

A function ff maps the set of natural numbers to whole numbers, such that f(xy)=f(x)f(y)+f(x)+f(y)f(xy) = f(x)f(y) + f(x) + f(y) for all x,yx, y and f(p)=1f(p) = 1 for every prime number pp. Then, the value of f(160000)f(160000) is

  1. A.

    1023

  2. B.

    4095

  3. C.

    2047

  4. D.

    8191

Answer

B

Explanation

Adding 1 to both sides of the functional equation: f(xy)+1=f(x)f(y)+f(x)+f(y)+1f(xy) + 1 = f(x)f(y) + f(x) + f(y) + 1 f(xy)+1=(f(x)+1)(f(y)+1)f(xy) + 1 = (f(x) + 1)(f(y) + 1)

Let g(n)=f(n)+1g(n) = f(n) + 1. Then g(xy)=g(x)g(y)g(xy) = g(x)g(y). For any prime pp, f(p)=1    g(p)=f(p)+1=2f(p) = 1 \implies g(p) = f(p) + 1 = 2.

Prime factorization of 160000160000: 160000=16×104=24×(2×5)4=28×54160000 = 16 \times 10^4 = 2^4 \times (2 \times 5)^4 = 2^8 \times 5^4

Using the multiplicative property of gg: g(160000)=g(28×54)=(g(2))8×(g(5))4=28×24=212=4096g(160000) = g(2^8 \times 5^4) = (g(2))^8 \times (g(5))^4 = 2^8 \times 2^4 = 2^{12} = 4096

Since f(n)=g(n)1f(n) = g(n) - 1: f(160000)=40961=4095f(160000) = 4096 - 1 = 4095.

Practise this under exam conditions

Sign in to solve it with a live timer, the on-screen CAT calculator, and streak and accuracy tracking across every question you attempt.

Solve in the workspace