N^3 mod t covers all remainders?

  • Thread starter Thread starter Gerenuk
  • Start date Start date
Gerenuk
Messages
1,027
Reaction score
5
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?
 
Physics news on Phys.org
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}
 
I think the answer is when t is a square free product of primes of the form 2, 3 or 6k-1.
 
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?
 
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.
 
The matter is extremely simply, if 3 is relatively prime to the order of the group mod p.
 
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?
 
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.
 
Last edited:
Gerenuk said:
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.
 
Last edited:
  • #10
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.
 
  • #11
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.
 
  • #12
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.)
 
  • #13
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?
 
  • #14
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 6mod12[/tex]<br /> <br /> but the previous posts say it may not be possible. (In fact it isn&#039;t.)
 
  • #15
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.
 
Last edited:
  • #16
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.
 
  • #17
robert Ihnot said:
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.
 
Last edited:
  • #18
The proof I included will immediately generalize to rth 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
Jarle said:
... 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).

Jarle said:
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?
 
  • #19
Martin Rattigan said:
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.

Martin Rattigan said:
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.
 
  • #20
Jarle said:
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.

Jarle said:
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?
 
  • #21
Martin Rattigan said:
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 &lt; p, 0 \leq a,b &lt; P. First, this implies that m = n modulo p by hypothesis, so m=n. However, m+ap for 0 \leq a &lt; 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.
 
Last edited:
  • #22
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.
 
Back
Top