# Congruence Relation proof over two integer variables

The original problem of yesterday that I set out to prove rigorously:

There is exactly $$k$$ unique values of: $$\quad {\Bigl\{\frac{p_n+1}{k}}\Bigr\}+{\Bigl\{\frac{p_n+k-1}{k}}\Bigr\}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(E0)$$ $$\quad \forall n \in \mathbb N \quad \operatorname{if and only if} \quad k \in \mathbb P \,\cup\,{\{1}\}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(0)$$

Where $${\{x}\}$$ is the fractional part of $$x$$.

EDIT @ 10/10/2018

I feel that although it is not going to suffice for complete proof, the following consequence of Wilson's theorem does indeed show the same principle at play, with only two unique values for the fractions described:

Wilson's theorem asserts that for $$\forall n \geq p$$

$${\Biggl\{\frac { \left( n! \right) ^{2}- \left( -1 \right) ^{n+1}}{p}}\Biggr\}={\frac { \left( p-1 \right) \left( 1-\delta \left(\frac{n}{2},\Bigl\lfloor \frac{n}{2} \Bigr\rfloor \right) \right) +\delta \left( \frac{n}{2},\Bigl\lfloor \frac{n}{2} \Bigr\rfloor \right) }{p}}\quad\quad\quad\quad\quad\quad\quad(\operatorname{WILSON001)}$$

This can be quickly verified by noting that the substitution $$n \rightarrow n\cdot p$$ into $$\operatorname{(WILSON001)}$$ allows us to make the same assertion, but for $$\forall n \in \mathbb N$$, for any prime $$p$$: $${\Biggl\{{\frac { \left( \left( np \right) ! \right) ^{2}- \left( -1 \right) ^ {np+1}}{p}}}\Biggr\}={\frac { \left( p-1 \right) \left( 1-\delta \left(\frac{n}{2},\Bigl\lfloor \frac{n}{2} \Bigr\rfloor \right) \right) +\delta \left( \frac{n}{2},\Bigl\lfloor \frac{n}{2} \Bigr\rfloor \right) }{p}} \quad\quad\quad\quad\quad\quad\quad(\operatorname{WILSON002)}$$

Moving closer to the precise nature of the original question I posted, we have:

Let $$\mathcal K_{N,m,0}$$ be the cardinality of the finite set :

$$S_0= {\Biggl\{\frac { \left( (n\cdot p_k)! \right) ^{m}- \left( -1 \right) ^{n\cdot m+1}}{p_k}-\Biggl\lfloor \frac { \left( (n\cdot p_k)! \right) ^{m}- \left( -1 \right) ^{n\cdot m+1}}{p_k}\Biggr\rfloor:n \leq N \land k \leq N}\Biggr\}$$

I would conjecture that the congruence relation as follows to exist:

$$\mathcal K_{N,m,0}=\delta \left( \frac{m}{2},\Bigl\lfloor \frac{m}{2} \Bigr\rfloor \right) \left( -1 \right) ^{\delta \left( \frac{m}{2},\Bigl\lfloor \frac{m}{2} \Bigr\rfloor \right) }p_{{\pi \left( N \right) }} + \Bigl( 2-\delta \left( \frac{m}{2},\Bigl\lfloor \frac{m}{2} \Bigr\rfloor \right) \Bigr) \left( N-1 \right) \quad\quad\quad\quad\quad\quad\quad(\operatorname{WILSON003)}$$

$$\delta(x,y)$$ is the Kronecker delta function.

And if this is to be true, (my group theory competence currently well below par to do so with ease) The fact that the "inner sets" of $$S$$ are always singleto and this congruence existing should teach me something significant.

Let $$\mathcal K_{N,m,1}$$ be the cardinality of the finite set :

$$S_1= {\Biggl\{\frac { \left( (n\cdot p_k)! \right) ^{m}\pm \left( -1 \right) ^{n}}{p_k}-\Biggl\lfloor \frac { \left( (n\cdot p_k)! \right) ^{m}\pm \left( -1 \right) ^{n}}{p_k}\Biggr\rfloor:n \leq N \land k \leq N}\Biggr\}$$

we have:

$$\mathcal K_{N,m,1}=2N-1$$

$$\delta(x,y)$$ is the Kronecker delta function.

From this point, the following refers to this total number of unique values of $$(E0)$$ over all $$n \in \mathbb N$$ that exist for a particular $$k \in \mathbb N$$ as $$\mathcal K_{k}$$.

The following inequality states the same conjecture in a more general sense, in terms of the total number of divisors:

$$\tau(k)-1 \leq\mathcal K_{k} \leq \tau(k)+k-2\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\,\,\,(1)$$

Other relevant lemma:

$$k \in {\{2^{j}:j \in \mathbb N \land j \neq 2}\} \Rightarrow \mathcal K_{k}=\varphi(k)\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\,\,\,\,(2)$$

$$K \leq k \leq 2K \Rightarrow \mathcal K_{k} \geq \varphi(K)\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad,\,\quad\quad\quad\,\,(3)$$

$$\mathcal K_{k} \lt \sigma(k)\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(4)$$

$$\forall x \in \mathbb R,$$ there is exactly one $$n \in {\{1,2,3,...,N}\}$$ such that: $$1-{\frac {n}{N}}\leq {\{x}\} \lt 1-\frac{n-1}{N} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\,\,\,\,(5)$$ $$\Bigl\lfloor {\frac {p_{{n}}+1}{p_{{n}}}} \Bigr\rfloor+ \Bigl\lfloor {\frac {2\,p_{{n}}-1}{p_{{n}}}} \Bigr\rfloor=2\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\,\,\,\,\,(6)*$$

$$*$$ Substitution of $$k=p_n$$ into $$(E0)$$ confirms this lemma to be true, as well as there being only one value possible for $$(E0)$$ when $$k=p_n$$.

Where $$\tau(N)$$ is the number of divisors of $$N$$.

Where $$\varphi(N)$$ is the totient of $$N$$.

Where $$\sigma(N)$$ is the sum of the divisors of $$N$$.

If we generalize to $$\mathcal K_{k,l}$$ being the number of unique values of: $${\Bigl\{\frac{p_n+l}{k}}\Bigr\}+{\Bigl\{\frac{p_n+k-l}{k}}\Bigr\}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(E1)$$ on $$n,l \in \mathbb N$$, $$(2)$$ is still true for any $$l$$, which could be verified by the congruence relation $$(0)$$ being true, thus this demonstrating the property of translation as we expect from a congruence relation.That is:

$$\mathcal K_{k,l}=k \,\,\forall n,l \in \mathbb N \operatorname{iff} k \in \mathbb P\cup {\{1}\}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(8)$$

The plot below more clearly demonstrates the reduction in unique values of the expression defined at $$(E0)$$ having proportion to the number of divisors of $$k$$, by defining two variations of $$(E0)$$, one consisting of only prime variables and the other having two natural number variables, the difference in their number of unique values in $${\{1,2,3,...,N}\}$$ being plotted against $$N$$.

Figure 1.0) Figure 1.1)

Further generalising the form originally stated,if we let $$\mathcal K_{k,l}$$ be the number of unique values of: $${\Bigl\{\frac{n+l}{k}}\Bigr\}+{\Bigl\{\frac{n+k-l}{k}}\Bigr\}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(E2)$$

The following deductions can then be made in looking at the ordered pairs generated by this arithmetic function:

We denote $$\mathcal L_0(N)$$ the total number of ordered pairs $$(n,k)$$ such that:$${\Biggl\{\frac{p_n+1}{k}}\Biggr\}\lt{\Biggl\{\frac{p_n+k-1}{k}}\Biggr\} \land n \leq N \land k \leq N$$

We denote $$\mathcal G_0(N)$$ the total number of ordered pairs $$(n,k)$$ such that:$${\Biggl\{\frac{p_n+1}{k}}\Biggr\}\gt{\Biggl\{\frac{p_n+k-1}{k}}\Biggr\} \land n \leq N \land k \leq N$$

We denote $$\mathcal E_0(N)$$ the total number of ordered pairs $$(n,k)$$ such that:$${\Biggl\{\frac{p_n+1}{k}}\Biggr\}={\Biggl\{\frac{p_n+k-1}{k}}\Biggr\} \land n \leq N \land k \leq N$$

Naturally we have:

$$\mathcal L_0(N)+\mathcal E_0(N)+\mathcal G_0(N)=N^2$$

$$\mathcal E_0(N)=N^2-N(N-2)=2N$$

Recalling the lemma:

$$\not\exists\, k \in \mathbb N\, \operatorname{s.t}\quad {\Bigl\{\frac{p_n+1}{k}}\Bigr\}={\Bigl\{\frac{p_n+k-1}{k}}\Bigr\}\land k \neq 2\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(\operatorname{lulu001})$$

It is clear that the $$2N$$ values for which $${\Biggl\{\frac{p_n+1}{k}}\Biggr\}={\Biggl\{\frac{p_n+k-1}{k}}\Biggr\}$$ all occur when $$k=2$$.

We denote $$\mathcal L_1(N,K)$$ the total number of ordered pairs $$(n,k)$$ such that:$${\Biggl\{\frac{p_n+1}{k}}\Biggr\}\lt{\Biggl\{\frac{p_n+k-1}{k}}\Biggr\} \land n \leq N \land 2\lt k \leq K$$

We denote $$\mathcal G_1(N,K)$$ the total number of ordered pairs $$(n,k)$$ such that:$${\Biggl\{\frac{p_n+1}{k}}\Biggr\}\gt{\Biggl\{\frac{p_n+k-1}{k}}\Biggr\} \land n \leq N \land 2\lt k \leq K$$

We denote $$\mathcal E_1(N,K)$$ the total number of ordered pairs $$(n,k)$$ such that:$${\Biggl\{\frac{p_n+1}{k}}\Biggr\}={\Biggl\{\frac{p_n+k-1}{k}}\Biggr\} \land n \leq N \land 2\lt k \leq K$$

Since:

$$\mathcal E_1(N,K)=0$$

We have:

$$\mathcal L_1(N,K)+\mathcal G_1(N,K)=N(K-2)$$

The linear asymptotic relation seen in Figure 1.1) is currently something I have deemed to be intimately related to another project I consider to be important, and I have added this to the question about this project which I will link here

We now define a set: $$S_l={\{\mathcal K_{n,k,l}:n,k \in \mathbb N}\}$$ for some fixed $$l \in \mathbb N$$,all elements of: $$S_l \,\backslash\, (S_{l-1} \cap S_{l-2} \cap S_{l-3} \cdot \cdot \cdot \cap S_{1})\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(9)$$ Are even numbers greater than $$4$$.

Another point of interest is the set: $$(S_{l-1} \cup S_{l-2} \cup S_{l-3} \cdot \cdot \cdot \cup S_{1}) \,\backslash \,S_l\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(10)$$

As with the set defined in $$(5)$$, all elements of these sets are even numbers.

Now as far as I am capable of doing at this point in time, a direct proof would be computation of the Discrete Fourier Transform (DFT) for the expression $$\mathcal K_{k}$$, I am able to find one readily for the expression for which $$\mathcal K_{k}$$ counts the number of unique values of, however this will be quite cumbersome, and so I can only assume that the DFT for $$\mathcal K_{k}$$ will be a complete nightmare. None the less, I would consider this a legitimate means of proof.

so that is as far as I have got, I am looking for a more simple elementary proof at this point, so I am looking for hints there.