Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

N^3 mod t covers all remainders?

  1. Apr 13, 2010 #1
    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
    [tex]n^3\quad\text{mod}\quad t[/tex]
    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?
  2. jcsd
  3. Apr 13, 2010 #2
    t would be found when solving the system of equations:

    [tex]n - n^3 = k_1t[/tex]
    [tex]n - n^3 - 1 = k_2t[/tex]
    [tex]n - n^3 - 2 = k_3t[/tex]
    [tex]-n^3 = k_nt[/tex]

    [tex](k_1, \cdots, k_n) \in \mathbb{Z}[/tex]
  4. Apr 13, 2010 #3
    I think the answer is when t is a square free product of primes of the form 2, 3 or 6k-1.
  5. Apr 13, 2010 #4
    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?
  6. Apr 13, 2010 #5
    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.
  7. Apr 13, 2010 #6
    The matter is extremely simply, if 3 is relatively prime to the order of the group mod p.
  8. Apr 13, 2010 #7
    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?
  9. Apr 13, 2010 #8
    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: [tex] a^{_(p-1)}\equiv 1 \bmod p[/tex].

    It is said that a belongs to b, if b is the lowest power such that [tex]a^b\equiv 1\bmod p[/tex] 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 [tex]a^{_md+n(p-1)}\equiv1x1 \equiv a^1 \bmod p[/tex]. Which is to say, d must be 1.
    Last edited: Apr 14, 2010
  10. Apr 14, 2010 #9
    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: Apr 14, 2010
  11. Apr 15, 2010 #10
    Given [itex]t\in N[/itex] the numbers modulo [itex]t[/itex], [itex]Z_t[/itex] form a semigroup under multiplication. This semigroup decomposes into two disjoint subsemigroups, say [itex]\Phi_t,\Psi_t[/itex], being respectively the numbers relatively prime to [itex]t[/itex] and the rest. The former is actually a group.

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

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

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

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

    If [itex](r,s)=1[/itex], [itex]\Phi_{rs}\cong \Phi_r\bigotimes \Phi_s[/itex] as groups. So [itex]n^3[/itex] will not represent all of [itex]Z_t[/itex] if [itex]t[/itex] has any prime factor [itex]t=6k+1[/itex]. Morover if has a square factor, say [itex]t=s^2u, s>1[/itex], then [itex](su)\neq 0(t)[/itex], but [itex](su)^3=0(t)[/itex], hence [itex]\kappa:\Psi(t)\rightarrow \Psi_t[/itex] 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 [itex](n,t)=1[/itex] and [itex]t[/itex] is of the given form.
  12. Apr 15, 2010 #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.
  13. Apr 17, 2010 #12
    The rest is just the Chinese remainder theorem.

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

    (I thought I saw a problem with this when I first posted, but b*!!"@ed if I can now.)
  14. Apr 17, 2010 #13
    I am not sure I can even understand your first line about [tex] t=p_1p_2\dots p_r[/tex] What is the given n?

    What does this have to do with finding a solution to [tex]x^3\equiv6\bmod12[/tex]?
  15. Apr 18, 2010 #14
    In the previous post I proved that all integers are cubic residues mod [itex]t[/itex] only if [itex]t[/itex] is a square free product of primes of the form [itex]2,3[/itex] or [itex]6k-1[/itex]. Also that all integers relatively prime to [itex]t[/itex] are cubic residues mod [itex]t[/itex] if [itex]t[/itex] is a square free product of primes of the form [itex]2,3[/itex] or [itex]6k-1[/itex], and if [itex]t[/itex] is just a prime of the form [itex]2,3[/itex] or [itex]6k-1[/itex] then all integers are cubic residues mod [itex]t[/itex].

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

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

    Since [itex]12[/itex] is not square free, the last post is not relevant to finding a solution of

    [itex]x^3\equiv 6[/itex]mod[itex]12[/tex]

    but the previous posts say it may not be possible. (In fact it isn't.)
  16. Apr 23, 2010 #15


    User Avatar
    Science Advisor

    In general, using the group properties of [tex]\mathbb{Z}_p / \{ 0 \}[/tex] there are [tex]1+\frac{p-1}{\gcd(p-1,r)}[/tex] different r'th powers modulo prime p. This is true by the fact that the order of any non-zero number modulo p divides [tex]\phi(p)=p-1[/tex]. Thus n^3 will generate all remainders modulo p as long as [tex]\gcd(p-1,3)=1[/tex], 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 [tex]p_i[/tex], namely that [tex]\gcd(p_i-1,r) = 1[/tex].
    Last edited: Apr 23, 2010
  17. Apr 24, 2010 #16
    [tex]1+\frac{p-1}{\gcd(p-1,r)} [/tex]

    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.
  18. Apr 24, 2010 #17


    User Avatar
    Science Advisor

    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: Apr 24, 2010
  19. Apr 26, 2010 #18
    The proof I included will immediately generalize to rth powers by excluding primes such that [itex](r,p-1)\neq 1[/itex] from the factorization of [itex]t[/itex] in place of primes of the form [itex]6k+1[/itex].

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

    Is what Jarle has in mind here is an application of the Chinese remainder theorem?
  20. Apr 26, 2010 #19


    User Avatar
    Science Advisor

    Erm, I can hardly see a correction here. I did state that it followed from the group properties of [tex]\mathbb{Z}_p / \{ 0 \}[/tex], which includes the fact that the group 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.
  21. Apr 27, 2010 #20
    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 [itex]\mathbb{Z}_p - \{0 \}[/itex] is cyclic.

    This appears to be the main part of your proof. How would you do it?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook