N^3 mod t covers all remainders?

[Gerenuk]

As a generalization to some problem I've just seen, I'm wonder what the solution to the following question is:

For which t does
$$n^3\quad\text{mod}\quad t$$
cover all remainders?

For example it works for t=5 since n^3 mod 5 yields all of 0...4
Is there a general formula for possible t?

 

[epkid08]

t would be found when solving the system of equations:

$$n - n^3 = k_1t$$
$$n - n^3 - 1 = k_2t$$
$$n - n^3 - 2 = k_3t$$
$$\vdots$$
$$-n^3 = k_nt$$

$$(k_1, \cdots, k_n) \in \mathbb{Z}$$

 

[Martin Rattigan]

I think the answer is when t is a square free product of primes of the form 2, 3 or 6k-1.

 

[Gerenuk]

Oh, seems to work for my first little brute force test (testing a few number only).

Is it easy to show why your answer is correct?

 

[Gerenuk]

I'm not sure how to interpret your solution, epk, because n is all numbers together and the question is whether all n are able to cover all remainders.

 

[robert Ihnot]

The matter is extremely simply, if 3 is relatively prime to the order of the group mod p.

 

[Gerenuk]

I only know the very basic terms. What does "to the order of the group mod p" mean? And how do I get Martins solution from that?

 

[robert Ihnot]

The order of the group is simply the number of elements present in the multiplicative group. For a prime p, it is p-1. It is also by Fermat's Little Theorem the power such that for all multiplicative elements: $$a^{_(p-1)}\equiv 1 \bmod p$$.

It is said that a belongs to b, if b is the lowest power such that $$a^b\equiv 1\bmod p$$ It turns out that b will be a divisior of p-1. The proof of that is rather simple. Let us suppose that there exixsts a d>1 of this type that does not divide p-1. Then we know that there are integers,positive or negative, m, n such that m(d)+n(p-1) = 1. Then we have $$a^{_md+n(p-1)}\equiv1x1 \equiv a^1 \bmod p$$. Which is to say, d must be 1.

 

[Martin Rattigan]

Is it easy to show why your answer is correct?

The answer is, I don't know.

I thought I had a fairly straightforward proof, but I noticed a law in the flogic just before I posted, hence the lack of proof and tentative wording in that post.

I will attempt to shore up the proof, but that may have to wait until weekend. In the meantime I've run a computer check on the numbers up to 50,000 without finding any counter-examples. I'm running the check up to 1,000,000 on a different machine but because it's a BFI Javascript routine and a slow machine that could take a while.

The proof that every number is a cube mod t only if t is a square free product of primes of the form 2, 3 and 6k-1 and that n is a cube mod t whenever (n,t)=1 and t is of the given form are straightforward, and I'll post that (or hopefully a proof of the whole result) later.

 

[Martin Rattigan]

Given $t\in N$ the numbers modulo $t$, $Z_t$ form a semigroup under multiplication. This semigroup decomposes into two disjoint subsemigroups, say $\Phi_t,\Psi_t$, being respectively the numbers relatively prime to $t$ and the rest. The former is actually a group.

The mapping $\kappa:Z_t\rightarrow Z_t$ s.t. $\kappa:n\mapsto n^3$ is a semigroup endomorphism of $Z_t$, and because $((n^3,t)=1)\equiv ((n,t)=1)$, it's also a semigroup endomorphism of both $\Phi_t$ and $\Psi_t$. Then $n^3$ will represent all of $Z_t$ iff $\kappa:\Phi_t\rightarrow \Phi_t$ and $\kappa:\Psi_t\rightarrow \Psi_t$ are both isomorphisms (by the Pigeonhole Principle).

$\kappa$ is a group endomorphism of $\Phi_t$, and will be an isomorphism iff the kernel, $\{n\in Z_t:n^3=1\}$ is just $(e)$. By Lagrange and Cauchy's theorems this will be the case iff $3\nmid o(\Phi_t)$.

If $t$ is prime then $\Psi_t$ is just $\{0$ mod $t\}$, and $\kappa$ is necessarily an isomorphism on $\Psi_t$. In this case $o(\Phi_t)=t-1$.

All primes other than $2$ and $3$ are of the form $6k\pm 1$, so only when $t=6k+1$ will $3\mid t-1$. Thus $n^3$ will represent all of $Z_t$ for primes $2$, $3$ and $t=6k-1$.

If $(r,s)=1$, $\Phi_{rs}\cong \Phi_r\bigotimes \Phi_s$ as groups. So $n^3$ will not represent all of $Z_t$ if $t$ has any prime factor $t=6k+1$. Morover if has a square factor, say $t=s^2u, s>1$, then $(su)\neq 0(t)$, but $(su)^3=0(t)$, hence $\kappa:\Psi(t)\rightarrow \Psi_t$ cannot be an isomorphism.

This proves that every number is a cube mod t only if t is a square free product of primes of the form 2, 3 and 6k-1 and that n is a cube mod t whenever $(n,t)=1$ and $t$ is of the given form.

 

[Martin Rattigan]

The rest will have to wait till weekend unless somebody else completes it. I killed the Javascript routine at just over 250,000 by the way, because it was obviously not going to make even 500,000 before bedtime. Hypothesis held good up to there.

 

[Martin Rattigan]

The rest is just the Chinese remainder theorem.

If $t=p_1p_2\dots p_r$, where the $p_i$ are distinct primes of the form $2, 3$ or $6k-1$, then given $n$, for each $i$ we can find an $m_i$ such that $m_i^3=n(p_i)$. There is then an $m(t)$ such that for each $i$, $m=m_i(p_i)$. For each $i$, $m^3=n(p_i)$, so $m^3=n(t)$.

(I thought I saw a problem with this when I first posted, but b*!"@ed if I can now.)

 

[robert Ihnot]

I am not sure I can even understand your first line about $$t=p_1p_2\dots p_r$$ What is the given n?

What does this have to do with finding a solution to $$x^3\equiv6\bmod12$$?

 

[Martin Rattigan]

In the previous post I proved that all integers are cubic residues mod $t$ only if $t$ is a square free product of primes of the form $2,3$ or $6k-1$. Also that all integers relatively prime to $t$ are cubic residues mod $t$ if $t$ is a square free product of primes of the form $2,3$ or $6k-1$, and if $t$ is just a prime of the form $2,3$ or $6k-1$ then all integers are cubic residues mod $t$.

To prove my original assertion, it remains to show that all integers are cubic residues mod $t$ if $t$ is a square free product of primes of the form $2,3$ or $6k-1$.

To this end the first line specifies that $t$ is of the required form and chooses $n$, which can be any integer, which we require to show is a cubic residue mod $t$.

Since $12$ is not square free, the last post is not relevant to finding a solution of

$x^3\equiv 6$mod[itex]12[/tex]<br /> <br /> but the previous posts say it may not be possible. (In fact it isn't.)[/itex]

 

[disregardthat]

In general, using the group properties of $$\mathbb{Z}_p / \{ 0 \}$$ there are $$1+\frac{p-1}{\gcd(p-1,r)}$$ different r'th powers modulo prime p. This is true by the fact that the order of any non-zero number modulo p divides $$\phi(p)=p-1$$. Thus n^3 will generate all remainders modulo p as long as $$\gcd(p-1,3)=1$$, i.e whenever p = 2 modulo 3, or p = 3.

Some simple observations will yield that n^3 will generate all remainders modulo t whenever t is not divisible by any square by matching up remainders to t's respective prime divisors (which all must equal 2 modulo 3). A proof is easily found by induction on the number of prime factors.

This can easily be generalized to r'th powers by using the formula given above. It places explicit restrictions on the prime divisors $$p_i$$, namely that $$\gcd(p_i-1,r) = 1$$.

 

[robert Ihnot]

$$1+\frac{p-1}{\gcd(p-1,r)}$$

I don't know that I see the above. For example modulo 7 there is only one element of order 2, which is 6. But your formula suggests to me 3.

 

[disregardthat]

$$1+\frac{p-1}{\gcd(p-1,r)}$$

I don't know that I see the above. For example modulo 7 there is only one element of order 2, which is 6. But your formula suggests to me 3.

The formula gives the number of different r'th power remainders modulo p. For example, if you tried p = 7, and r = 2, that gives the quadratic remainders 0, 1 ,4, 9 = 2, 16=2, 25 = 4, 36 = 1 i.e. 0,1,2,4. The formula suggests 1 + 6/2 = 4, which is correct.

Considering the third powers, we have only 3 as the formula suggests, namely 0,1,6.

 

[Martin Rattigan]

The proof I included will immediately generalize to r^th powers by excluding primes such that $(r,p-1)\neq 1$ from the factorization of $t$ in place of primes of the form $6k+1$.

Morover the formula $1+\frac{p-1}{(p-1,r)}$ that Jarle includes gives the size of the image of the mapping $\kappa:\Phi_p\rightarrow \Phi_p$ that I referred to plus $1$ for the image of $\kappa:\Psi_p\rightarrow \Psi_p$. The formula relies on the fact that the group ${\mathbb Z}_p-\{0\}$ is cyclic (i.e. the existence of a primitive root) rather than just

... by the fact that the order of any non-zero number modulo p divides $$\phi(p)=p-1$$.

as Jarle states.

It is not necessary to assume the existence of primitive roots to prove the result required. (The proof I included doesn't).

Some simple observations will yield that n^3 will generate all remainders modulo t whenever t is not divisible by any square by matching up remainders to t's respective prime divisors (which all must equal 2 modulo 3). A proof is easily found by induction on the number of prime factors

Is what Jarle has in mind here is an application of the Chinese remainder theorem?

 

[disregardthat]

The formula relies on the fact that the group ${\mathbb Z}_p-\{0\}$ is cyclic (i.e. the existence of a primitive root) rather than just

... by the fact that the order of any non-zero number modulo p divides $$\phi(p)=p-1$$

as Jarle states.

Erm, I can hardly see a correction here. I did state that it followed from the group properties of $$\mathbb{Z}_p / \{ 0 \}$$, which includes the fact that the group is cyclic.

Is what Jarle has in mind here is an application of the Chinese remainder theorem?

Many ways lead to rome. Using the fact that the factors are relatively prime you can easily match up corresponding remainders. No need for an overkill.

 

[Martin Rattigan]

Erm, I can hardly see a correction here. I did state that it followed from the group properties of $$\mathbb{Z}_p / \{ 0 \}$$, which includes the fact that the group is cyclic.

I wanted to make the point that the result could be proved without using the fact that primitive roots exist. In your post there was no indication that the assumption of the existence of primitive roots was necessary for the proof you outline; the sentence I quoted from your post in fact tends to suggest that it isn't.

Gerenuk has claimed to know only the very basic terms, so could be unaware that $\mathbb{Z}_p - \{0 \}$ is cyclic.

Many ways lead to rome. Using the fact that the factors are relatively prime you can easily match up corresponding remainders. No need for an overkill.

This appears to be the main part of your proof. How would you do it?

 

[disregardthat]

This appears to be the main part of your proof. How would you do it?

One way could be by induction:

Let P be a product of k primes such that the hypothesis is true for all products of length less than or equal to k, and Pp a new product of k+1 primes, where p is a suitable prime relatively prime to P. Suppose $$(m+ap)^r=(n+bp)^r \pmod{Pp}$$ for $$0 \leq m,n < p, 0 \leq a,b < P$$. First, this implies that m = n modulo p by hypothesis, so m=n. However, m+ap for $$0 \leq a < P$$ are P different elements modulo P (as p is relatively prime to P), so $$(m+ap)^r$$ are different modulo P by hypothesis, which means a=b, and thus m+ap=n+bp.

 

[Martin Rattigan]

Yes that's a fairly straightforward direct proof that makes no reference to the Chinese remainder theorem, so could be regarded as preferable to the proof I gave.