Maths Olympiad Prep

Library / /21 of 23

Number theory Difficulty 7.3 National olympiad, round 2 Prove it Ireland

A function f:ZZf: \mathbb{Z} \rightarrow \mathbb{Z} is called *loggy* if it satisfies the following two conditions:
(i) f(xy)f(x)+f(y)(mod8)f(xy) \equiv f(x) + f(y) \pmod{8} for all x,yZx, y \in \mathbb{Z} that are not divisible by 1717;
(ii) f(x+17)f(x)(mod8)f(x + 17) \equiv f(x) \pmod{8} for all xZx \in \mathbb{Z}.
Determine, with proof,

a. if there exists a loggy function for which f(2)=1f(2) = 1;
b. if there exists a loggy function for which f(3)=1f(3) = 1.

Solution

a. Because 622(mod17)6^2 \equiv 2 \pmod{17}, conditions (i) and (ii) imply
f(2)f(62)2f(6)(mod8) f(2) \equiv f(6^2) \equiv 2f(6) \pmod{8}
If a loggy function ff satisfies f(2)1(mod8)f(2) \equiv 1 \pmod{8}, we get 2f(6)1(mod8)2f(6) \equiv 1 \pmod{8}. But the congruence 2x1(mod8)2x \equiv 1 \pmod{8} has no solution xZx \in \mathbb{Z}. Hence, there does not exist a loggy function satisfying f(2)=1f(2) = 1.

b. Note that (ii) implies that f(xn)nf(x)(mod8)f(x^n) \equiv nf(x) \pmod{8} for all xx that are not divisible by 1717. In particular, f(3n)nf(3)(mod8)f(3^n) \equiv nf(3) \pmod{8}. If f(3)=1f(3) = 1, this means that for all positive integers nn we need to have f(3n)n(mod8)f(3^n) \equiv n \pmod{8}.
We claim that each integer xx that is not divisible by 1717 is congruent to 3n(mod17)3^n \pmod{17} with a unique 1n161 \le n \le 16. The reason is that the multiplicative order of 33 (mod 1717) is equal to 1616. In other words, no two of the numbers 3n,n=1,2,,163^n, n = 1, 2, \dots, 16 are congruent (mod 1717). To see this, suppose 3a3n(mod17)3^a \equiv 3^n \pmod{17} for some 1a161 \le a \le 16. If d=gcd(a,16)d = \gcd(a, 16), there exist positive integers r,sr, s such that either ar=d+16sar = d + 16s, or 16s=d+ar16s = d + ar. Because 3a3161(mod17)3^a \equiv 3^{16} \equiv 1 \pmod{17} both equations imply 3d1(mod17)3^d \equiv 1 \pmod{17}. As dd is a factor of 1616, we just check
329(mod17),344(mod17),381(mod17) 3^2 \equiv 9 \pmod{17}, \quad 3^4 \equiv -4 \pmod{17}, \quad 3^8 \equiv -1 \pmod{17}
to see that d=16d = 16 and so a=16a = 16 as well. Therefore, if 1mn161 \le m \le n \le 16 and 3m3n(mod17)3^m \equiv 3^n \pmod{17}, we have 3nm1(mod17)3^{n-m} \equiv 1 \pmod{17} and mnm \ne n would imply nm=16n-m=16, which is impossible.
Define a function f:ZZf: \mathbb{Z} \to \mathbb{Z} as follows:
f(x)=0whenever x0(mod17) f(x) = 0 \quad \text{whenever } x \equiv 0 \pmod{17}
f(x)=nwhenever x3n(mod17) with 1n16. f(x) = n \quad \text{whenever } x \equiv 3^n \pmod{17} \text{ with } 1 \le n \le 16.
Because the value of ff depends only on xx (mod 1717), condition (i) is satisfied. The function is defined for all integers, because each integer that is not divisible by 1717 is congruent to a unique 3n(mod17)3^n \pmod{17}. Finally, to see that Condition (ii) holds, let mm and nn both be integers between 11 and 1616 and note that in case m+n>16m+n > 16, we have 3m+n3m+n16(mod17)3^{m+n} \equiv 3^{m+n-16} \pmod{17} by Fermat's Little Theorem and so
f(3m+n)=f(3m+n16)=m+n16m+n(mod8). f(3^{m+n}) = f(3^{m+n-16}) = m+n-16 \equiv m+n \pmod{8}.
Hence, we obtain the required
f(3m3n)=f(3m+n)m+nf(3m)+f(3n)(mod8). f(3^m \cdot 3^n) = f(3^{m+n}) \equiv m+n \equiv f(3^m) + f(3^n) \pmod{8}.
Therefore, this function is a loggy function that satisfies f(3)=1f(3) = 1.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.