Which integers have order 6 (mod 37)?

Question

Which integers have order $6\ (\text {mod}\ 37)$? I have tried expanding $x^6-1=0\ (\text {mod}\ 37)$ equation, i tried expanding it as $x^3-1$ and $x^3+1$ and I expanded further and tried to expand as adding $37$ to $x^6-1$ does alter as $\text {mod}\ 37$ is zero , but I could lead further.

Answer 1

HINT:

Try to use Fermats little theorem.

EDIT: By the above named theorem $x^{36}=(x^6)^6\equiv 1 \ \ \bmod 37$. Not surprisingly $x\equiv_{37}1$ is your first solution. $2^6=64\equiv_{37} 27$ so $27$ goes on the list. $3^6=3^2\cdot 3^2\cdot 3=81\cdot 3^2\equiv_{37}7\cdot 3^2\equiv_{37}26$ so $26$ goes also on the list. $4^6=(2^6)^2\equiv_{37}=27^2\equiv_{37}26$. And so on... You will be able to use already known information as soon as $x$ is a composite.

Answer 2

Look for a generator, which is any number $g$ such that $g^{12}\not\equiv 1$ and $g^{18}\not\equiv 1$. Here you get lucky, because the first number you try, $2$, is a generator. So now it's just $2^6$ and $2^{30}$.

Answer 3

As 6th powers, are also squares of cubes ( or cubes of squares), 6th powers will fall into one of the 19 quadratic residues mod 37: $$(0,1,4,9,16,25,36,12,27,7,26,10,33,21,11,3,34,30,28)$$ Now the question is, which of these cubed give a remainder of 1. We know each of these quadratic residues, represents x and -x squared. You'll note that in this case ( possibly any time modulus is prime, or 1 mod 4, or both), we can pair them up into additive inverse pairs ( will come in to play shortly). namely:$$((0,0),(1,36),(4,33),(9,28),(16,21),(25,12),(27,10),(7,30),(26,11),(3,34))$$

One property of cubes (or odd powers in general) mod anything, is that the additive inverse raised to that power, is the additive inverse of the number raised to that powers: $$x^{2n+1}\equiv-((-x)^{2n+1})$$ This plus the even power rule: $$x^{2n}\equiv(-x)^{2n}$$ allows to test 4 values with one test, for most testing As follows:$$x^6\equiv(-x)^6\equiv(-x^2)^3$$. The last parentheses has two square roots, Also the additive inverse of say 2 is -2, which is p-2 mod p. This is why you don't see all numbers less than 37 below, They are in their negative form. Let's get started: $$\begin{eqnarray}(0^2)^3\equiv((-0)^2)^3\equiv 0 \bmod 37\\(1^2)^3\equiv((-1)^2)^3\equiv-((-6)^2)^3)\equiv-(6^2)^3\equiv 1\bmod 37\\(15^2)^3\equiv((-15)^2)^3\equiv-((-16)^2)^3)\equiv-(16^2)^3\equiv 27\bmod 37\\(2^2)^3\equiv((-2)^2)^3\equiv-((-12)^2)^3)\equiv-(12^2)^3\equiv 27\bmod 37\\(9^2)^3\equiv((-9)^2)^3\equiv-((-17)^2)^3)\equiv-(17^2)^3\equiv 10\bmod 37\\(3^2)^3\equiv((-3)^2)^3\equiv-((-18)^2)^3)\equiv-(18^2)^3\equiv 26\bmod 37\\(11^2)^3\equiv((-11)^2)^3\equiv-((-8)^2)^3)\equiv-(8^2)^3\equiv 1\bmod 37\\(14^2)^3\equiv((-14)^2)^3\equiv-((-10)^2)^3)\equiv-(10^2)^3\equiv 36 ( aka -1) \bmod 37\\(7^2)^3\equiv((-7)^2)^3\equiv-((-5)^2)^3)\equiv-(5^2)^3\equiv 26\bmod 37\\(4^2)^3\equiv((-4)^2)^3\equiv-((-13)^2)^3)\equiv-(13^2)^3\equiv 26\bmod 37\\\end{eqnarray}$$

This gives 10,-10,1,-1,11,-11 Which are the 6th roots of 1 mod 37. EDIT: But not all are order 6 (my mistake) because some (-1,1, are sqrts as well, so 6 is not their order, -10,10 are cube roots, so 6 is not their order) don't require the full 6 multiplies to hit 1.

ADDENDUM: I'm adding this, to go over some basic rules of arithmetic. They are necessary for understanding the other answers, and similar problems. Here goes ( gulps):

You might know $$x-a+a=x$$ This is known as, the cancellation property of addition. It's used to represent x as a binomial, for the polynomial remainder theorem. You may know of FOIL, First-Inner-Outer-Last . This helps us apply the distributive property of addition over multiplication to polynomials. These form the basics of arithmetic.

Another rule of arithmetic, is That adding 0 doesn't change anything. This is an example of idempotent operations, operations that don't change a thing, another is multiplying by 1. You may also know, subtraction is simply adding an additive inverse, a value, or object, that when added to a certain value sums to 0.

Now to some exponentiation properties: $$a^na^m=a^{n+m}$$ This comes from the fact That if you multiply a set of n a's, and m a's you will be multiplying m+n a's together. We also have:$$(a^n)^m=a^{nm}$$ This follows from The previous rule, as exponents mean repeated multiplication, and repeated addition of the same thing is equivalent to multiplication by that thing.

Lastly, before the big theorems that underpin The answers here, we have three more rules: $$1^n=1$$ This applies for any n value. $$x^n=(-x)^n$$ holds if n is even. $$x^n=-((-x)^n)$$ if n is odd.

Yes, I've left a few out. Onto explaining the theory behind these answers.

First up, Polynomial Remainder Theorem. This is in effect, the recognition that evaluation of each term seperately in a binomial expansion, repeatedly applying FOIL, the only term that doesn't end up with the first term gauranteed to be a divisor of it, is multiplying all the Last together. As x=(x-a)+a , via The cancellation property of addition, this makes a the last term ( due to regrouping because the associative property of addition). In powers of this binomial, it will be a raised to the exponent in question. Due to addition of 0 being idempotent, and multiplication by 0 giving 0 (zero product rule) applying FOIL to $(z+0)(a^n+0)$ one last time, with z the coefficient, gives $za^n$ Which is the term evaluated at a. Doing this to each term gives the polynomial evaluated at a, as the remainder.

Next up Factor theorem. This says, if the polynomial evaluated at a, gives 0 (a would then be called a root,or a zero), Then (x-a) is a linear factor of the polynomial. By the previous theorem, and The very definition of a divisor, it follows.

Lastly, Chinese Remainder Theorem. This states, that given two congruences that must be met $py+b=cz+a$ then there is a unique congruence, mod the LCM of the moduli, That will satify both congruences.

These along with the fact, modular arithmetic won't violate basic arithmetic rules, is enough to show most of what is answered.

Here's the how:

Barry Cipra states a factorization of $x^3+1$ which can be shown to hold via Factor theorem, and polynomial long division. The quadratic, could probably use a modular arithmetic form of the quadratic formula like: $$x=(-b\pm\sqrt{b^2-4ac})2^{-1}a^{-1}$$ But, That involves taking Modular square roots.

My answer, simply uses arithmetic rules to cut down the grunt work, by matching things up.

Piquito Just uses actual work mostly.

Vinyl_coat_jawa uses repeat information to cut down brute force.

TonyK uses the fact that modular arithmetic obeys arithmetic rules, so 1 to any power is 1, and exponent addition and multiplication rules, plus an element that produces all values mod the number, because Modular arithmetic mod primes, forms what are called cyclic groups.

Answer 4

For problems like this, you should be willing to do some trial-and-error calculations, especially if you have no idea what else to do. At the very worst, you can compile a list of the powers $x^2$, $x^3$ and $x^6=(x^3)^2$ mod $37$ for each $x$ from $1$ to $18$. I wouldn't want to do this if the prime were $137$ instead of $37$, but a table with $54$ numbers on it can certainly be done by hand (with the help of a calculator, of course) on a single sheet of paper. Doing so, and being attentive to the patterns that arise, can be a valuable lesson in itself.

That said, the question remains, are there nice ways to reduce the amount of trial and error that's necessary? Here's one approach that cuts things down to doing around a dozen calculations.

The integers of order $6$ mod $37$ are among the roots of $x^6-1$, which factors as $(x^3-1)(x^3+1)$. We can ignore the $x^3-1$, since its roots are of order at most $3$. What remains factors as $(x+1)(x^2-x+1)$. We can ignore the $x+1$ as well, since its root, $-1$, is of order $2$. We are left looking for the roots of the quadratic $x^2-x+1$. These will be the integers of order $6$.

Now note that $x^2-x+1\equiv0$ mod $37$ if and only if $4x^2-4x+4\equiv0$ mod $37$, which can be rewritten as $(2x-1)^2+3\equiv0$ mod $37$. This reduces the problem to that of finding the two square roots of $-3$ mod $37$ (and then solving the equations $2x-1\equiv r_{1,2}$ mod $37$ for $x$).

This is the point at which you have to do some trial-and-error calculating, looking for a multiple of $37$ among the numbers $1^2+3$, $2^2+3$, $3^2+3$, up to $18^2+3$. But at least you don't have to take any powers higher than $2$. If there is a slick way to reduce the amount of trial and error (aside from skipping a bunch of small squares, for which $u^2+3$ has no chance of being divisible by $37$), I'd like to see it.

Answer 5

HINT.- $\mathbb F_{37}=\{\pm1,\pm2,\pm3,\cdots,\pm18,0\}$. Calculating till $11$ we get $$1^6=10^6=11^6=1$$ ans so is for the corresponding "negatives" (because of squares) then we have also $$36^6=27^6=26^6=1$$ There's no more because $$(11+x)^6=11^6+6\cdot11^5x+15\cdot11^4x^2+20\cdot11^3x^3+15\cdot11^2x^4+6\cdot11x^5+x^6=1$$ should imply $x=37$ since $11^6=1$