Is there always a permuted tuple of $n+1$ elements such that multiplying elementwise$\bmod n + 1$ on $(0, 1, \ldots, n)$ yields a binary $n+1$ tuple?

Question

Allow me to explain and give examples of something I've been playing around with.

Let $A$ be the $n+1$ tuple of the form $(0, 1, 2, \ldots, n)$. Let $k = n + 1$ be the number of elements.

My question is: is there a tuple $B$ which is a permutation of $A$ that when you multiply element-wise $AB \bmod k$ you get a binary tuple e.g. each element of the tuple $e_i \in \{0,1\}$?

An example is take $$A = (0,1,2), B = (0,1,2)$$ Then $$AB\bmod 3 = (0\cdot0, 1\cdot1, 2\cdot2) \bmod3 = (0, 1, 1)$$ since $0\cdot0 = 0\bmod3, 1\cdot1 = 1\bmod3, 2\cdot2=1\bmod3$. Then this $B$ is a possible solution. Note that $$B = (0,2,1)$$ is not a solution since $$AB\mod{3} = (0\cdot0, 1\cdot2, 2\cdot1)\bmod3 = (0, 2, 2).$$ I have found that up to $k=9$ there is always a permutation. The amount of permutations vary and this is what I have so far for each $k$ using a brute force program:

$$1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 4, 7: 7, 8: 4, 9: 18.$$

An example solution for $k=9$ is to take the permutation $$A = (0,1,2,3,4,5,6,7,8), B = (1, 0, 5, 6, 7, 2, 3, 4, 8)$$ which results in $$AB\mod{9} = (0,0,1,0,1,1,0,1,1).$$

There are some things I can immediately see such as any element can work in the 0th place since it will be multiplied by 0. Whereas only 0 and 1 work in the 1st place. Finding the 0s will happen when $ab\mid k$ and the 1s when $ab$ is coprime to $k$.

What I do not know and would love help on is:

1. Is there always a permutation that works for any $k > 9$?
2. Is there a way to find the number of permutations possible for each $k$? Like a formula to describe the sequence of permutation counts?
3. Is there a way to generate a permutation without brute force?

Answer 1

Such a permutation exists if and only if $k$ is $1$, $6$, $8$, $p$, or $p^2$ for some prime $p$, and if so, one such permutation has a simple explicit description.

The cases $k=1,6,8$ are easy. If $k=p$ or $k=p^2$, we can use the permutation $$\pi(x)=\begin{cases}x^{-1}&\gcd(x,k)=1,\\x&\text{otherwise.}\end{cases}$$

On the other hand, assume that $\pi$ is such a permutation for a given $k$. Then $$p\ge\varphi(k/p)$$ for all prime factors $p\mid k$: there are $\varphi(k/p)$ elements $x$ such that $\gcd(x,k)=p$, and $\pi$ maps these elements injectively into the set of all elements $y$ such that $py\equiv0\pmod k$, the number of which is $p$.

If $k$ is not a prime power, let $p_1<p_2<\dots<p_l$, $l\ge2$, be its prime divisors; then $$p_1\ge\varphi(k/p_1)\ge(p_2-1)\prod_{i>2}(p_i-1)>p_1$$ unless $l=2$ and $p_2-1=p_1$, i.e., $k=6$.

If $k=p^e$, $e\ge2$, then $$p\ge\varphi(p^{e-1})=p^{e-2}(p-1)>p$$ unless either $e=2$, or $e=3$ and $p=2$, i.e., $k=8$.

Answer 2

No. For $n=14$ it's not possible. There are at most $\phi(15)=8$ ones modulo $15$ in the product, and thus a least $15-8=7$ zeros. However, each zero must result from the product of numbers at least one of which is divisible by 5. We have only 6 multiples of 5 in the two permutations and thus getting 7 zeros is not possible.