Is the residue class of $f(n)$ modulo $n$ always an affine function of the prime factors of $n$?

37 Views Asked by At

Here is probably a simple question, I'd be thankful for an answer.

Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a certain integer-valued function, whose unknown we shall denote $n$. Assume the expression of $f$ is known, and it involves:

  • additions/soustractions (i.e. an affine part)
  • and an "affine-exponential" part (i.e. a sums of terms of the form $A_i(n)\times a_i^n$ for various integers $a_i$, where each $A_i(n)$ is affine in $n$).

Now what I would like to know is :

  1. does there necessarily exist an expression $g$ of the same type for the residue of $f(n)$ mod $n$ ?
  2. if yes, is it conceivable that some terms in this expression involve some but not all of the primes factors of $n$ rather than just always $n$ itself ?
  3. is there a method or some software to identify $g$ ?

In my application, $f$ is strictly increasing, if that helps.

As an explicit example (I didn't try to compute it, my application is longer so I prefer to avoid typing it all here for clarity), is is possible that $f(n)=1+(n+5)(n+7)(n+8)+(n+14)(n+21)\times 7^{3n+5}$ modulo $n$ can only be expressed as $g(n)=a+(n-qp)$ where $n$ has prime factorisation $n=qpr$, say ?