Assume that the first claim is false, we then prove the truth of the second claim. Letting n=p1α1…ptαt it follows that f(n)=f(p1)…f(pt). Thus, the value of f is only depending upon the values of f at prime points. Hence, it suffices to prove that for all large enough p, f(p)=1. Let us define the set A as follows:
A={an+b:f(an+b)=1,n∈N}
The first criterion ensures that A is nonempty. We shall prove that every large enough prime has a multiple in that set. Take n0, m0 such that an0+1=(ak+b)φ(a) and cm0+1=(ak+b)φ(c) then f(an0+1)=g(cm0+1)=1.
Then, if an+b∈A then
1=f((an+b)(an0+1))=f(a(ann0+bn0+n)+b)=g(c(ann0+bn0+n)+d).
Hence,
1=g(c(ann0+n+bn0)+d)g(cm0+1)=g(c(cm0(ann0+n+bn0)+(ann0+n+bn0)+dm0)+d)=f(a((cm0+1)(ann0+n+bn0)+dm0)+b).
That is, (cm0+1)(an0+1)(an+b)+(ad−bc)m0=s(an+b)+t∈A. That is, for all x∈A we shall have sx+t∈A. By choosing another n0 we can find another s1 such that s1x+t∈A for all x∈A. Now, take a large prime p and let us denote by b1,…,bk the residues of elements of A modulo p. Hence,
{s0b1+t,…,s0bk+t}≡{s1b1+t,…,s1bk+t}≡{b1,…,bk}(modp).
That is, s0(∑i=1kbi)+tk≡s1(∑i=1kbi)+tk≡∑i=1kbi(modp). Therefore, ∑i=1kbi≡0(modp) and k=p. That is, 0∈A. It yields that, there is a number of the form an+b in A that is a multiple of p. So, f(an+b)=1 implies that f(p)=1. By the same argument we find that g(p)=1. Taking D=∏q<pq, we are done. ■
Comment 1. The criterion that a, b, c, d are pair-wise coprime can be reduced to the condition ad=bc.
Comment 2. We can indeed prove that there is a positive integer D such that for all positive integers n, m, gcd(nm,D)=1 we have f(n)=g(m)=1. Here we provide the sketch of the solution. If f(an+b)=g(cn+d) for some positive integer n. Assume that gcd(a,b)=gcd(c,d)=1. Let p be a prime dividing an+b then gcd(a,p)=1 hence Pt=ptφ(a)=aTt+1 and f(Pt)=1. Hence,
g(cn+d)=f(an+b)=f(Pt)f(an+b)=f(a(nPt+bTt)+b)(1)
=g(c(nPt+bTt)+d),(2)
for all positive integers n, t. Let Sf={n:f(n)=1}, Sg={n:g(n)=1}.
It follows that c(nPt+bTt)+d∈Sg for each t. Now, we can prove the following interesting lemma that can be proved by use of techniques presented above.
Lemma. Let a, b, c, d be integers such that a, c>0, ad=bc. We define the set S as follows:
i. If x, y∈S, gcd(x,y)=1, then xy∈S,
ii. If x∈S, y∣x and gcd(yx,y)=1, then y∈S,
iii. an+b∈S if and only if cn+d∈S.
Let r be a prime number that doesn't divide ac and m be a positive integer such that {rm,rm+1,…} is a subset of S and there is a positive integer n such that cn+d∈S, for some positive integer n, there is a prime number q that doesn't divide ac and {1,q,q2,…}⊆S and all integers that are coprime to D=(ad−bc)gcd(a,c) are in S.
According to this interesting lemma, Nt={n∈N:gcd(n,c(ad−bc)Tt)⊆Sg, for all t∈N}. Now, using Chinese Remainder Theorem (CRT) to choose m0 such that gcd(am0+1,(ad−bc)T1)=1 and gcd(m0,T1)=2. Hence, {n∈N:gcd(n,c(ad−bc)m0)⊆Sg and therefore, {n∈N:gcd(n,2c(ad−bc))⊆Sg}. Continuing this way, we can prove that {n∈N:gcd(n,2a(ad−bc))⊆Sf. The rest is clear.