2
$\begingroup$

(There is a follow-up question at MO.)


Let $x\ \%\ m$ be the residue of $x$ modulo $m$, i.e.

$$x \equiv x\ \%\ m\pmod{m}$$

Let $\mu^n_m(x)$ denote multiplication by $n$ modulo $m$, i.e.

$$\mu^n_m(x) = nx\ \%\ m$$

Plotting $\mu^n_m(x)$ for $0 < n < m$ yields patterns with characteristic "slopes", here for $m=64$:

enter image description here
[click image to enlarge]

While one could define the slope of $\mu^n_m(x)$ to be just $n$, this is not, what the patterns reveal. So I was looking for a more appropriate definition of the slope of $\mu^n_m(x)$ and came up with the following definition:

Let $n_0$ be the number greater than $1$ which minimizes $(n_0 - 1)^2 + (\mu^n_m(n_0) - n)^2$. Define then the slope $s^n_m$ of $\mu^n_m(x)$ to be the number

$$s^n_m = (\mu^n_m(n_0) - n)/(n_0 - 1)\pmod{m},$$

the latter being a shortcut for

$$((n_0 - 1)s^n_m - \mu^n_m(n_0) + n)\ \%\ m = 0$$

I've chosen this definition for two reasons:

  1. Part 1 (the definition of $n_0$) considers the fact, that the dominant lines in the plot of $\mu^n_m(x)$ (which "show" the slope of the pattern) are those with a minimal number of parallels, i.e. a maximal distance between parallels, and thus the highest number of points on them, i.e. a minimal distance of points on them.

  2. You can apply the same definition for the non-modular case: the number $n_0>1$ that minimizes $(n_0 - 1)^2 + (n\cdot n_0 - n)^2 = (n_0 - 1)^2(1 + n^2)$ is always $2$ – independently of $n$ –, and the slope is accordingly $(n\cdot n_0 - n)/(n_0 - 1) = n$.

Find here the values for $n_0$ and $s^n_m$ for $m = 64$ and $0 < n < m$ together with the "visual" slopes of the dominant lines:

enter image description here

My question is:

Are there closed expressions for the values of $n_0$ and $s^n_m$ as defined above – as number theoretic functions of $n$ and $m$?

Furthermore:

What can be generally said about the slope $s^n_m$? When is it $0$ or $1$? When does it "jump" when going from $n$ to $n+1$?


To make clear that no regular pattern and no simple closed expression for $s^n_m$ is to be expected (except for $m$ prime), I plotted $s^n_{256}$ as shades of gray, from white for $s^n_{256} = 0$ to black for $s^{255}_{256} = 255$:

enter image description here

$\endgroup$
1
$\begingroup$

Observations for $m=64$:

$s^n_m = n$ with these exceptions

  • $s^n_m = 0$ for $n = k\cdot m/8$ with $k = 1,\dots,7$

  • $s^n_m = 1$ for $n = k\cdot m/4 + 1$ with $k = 0,\dots,3$

  • $s^n_m = n - m/2$ for $n = 34, 35, 47, 53,54$

Not very surprisingly one finds for prime numbers $p$ that $s^n_p = n$ for all $n$, e.g. for $p=61$:

enter image description here

Stated otherwise: $s^n_m = n$ for all $n < m$ iff $\mathbb{Z}/m\mathbb{Z}$ is a field.

In this respect, prime numbers behave like integers in non-modular arithemtic:

$$s^{n_1}_p = s^{n_2}_p \equiv n_1 = n_2$$

What's missing is a proof!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.