1
$\begingroup$

I want to make a sequence of numbers, where I pick the numbers $a_{0}, a_{1},..,a_{n}$. The length of the sequence is $n+1$.

Now I want the product of any pair of two numbers in the sequence modulo $k$ to be guaranteed to be unique and $k$ has to be as small as it can be in such a way that the resulting set has to be $\{r_{0},r_{1},\ldots,r_{k-1\}}$. So

$$a_{0}a_{1} \bmod k \rightarrow r_{0} \\ a_{0}a_{2} \bmod k \rightarrow r_{1} \\ a_{1}a_{2} \bmod k \rightarrow r_{2} \\ \vdots\\ a_{n-1}a_{n} \bmod k \rightarrow r_{k-1}$$

First I was thinking about using prime numbers, so that the products could be unique, but I have to find a property so that every product is not congruent to every other product.

To be more general: I am looking for a sequence of length $n$ and minimal $k$ such that

$\qquad \displaystyle |\{a_ia_j \mod k \mid 0 \leq i < j \leq n\}| = n(n+1)$.

So a mapping from every product mod k to "a value" filling up every number from $0$ to $k-1$.

|cite|improve this question
$\endgroup$
  • $\begingroup$ yes, thank you. Also ofcourse no combintation of 2, there are more combinations then number of elements. So just the maximum number of pairs in sequence of two. $\endgroup$ – Lee. M Jul 31 '12 at 8:41
  • 1
    $\begingroup$ Do you mean the product of two consecutive numbers? $\endgroup$ – A.Schulz Jul 31 '12 at 14:13
  • $\begingroup$ Any kind of numbers in the sequence grouped together like: {1,8,32} -> {{1,8},{1,32},{32,8}}. $\endgroup$ – Lee. M Jul 31 '12 at 15:02
  • 2
    $\begingroup$ So you want $n(n-1)/2$ products to be unique mod $n$ (or $n+1$)? That won't be possible unless $n$ is small. $\endgroup$ – Aryabhata Jul 31 '12 at 18:39
  • 1
    $\begingroup$ Finding a $k$ is not hard, if there is one. Compute all pairwise products in $\mathbb{N}$. If they are pairwise distinct, choose the maximum product plus one as $k$. If they are not distinct, there is no such $k$. $\endgroup$ – Raphael♦ Aug 1 '12 at 7:12

Your Answer

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

Browse other questions tagged or ask your own question.