- #1

- 11

- 0

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

In summary, the conversation discusses the proof that if x is both a quadratic nonresidue and a cubic nonresidue modulo 109, then x is guaranteed to be a primitive root modulo 109. This is proven by looking at the multiplicative group of 108 elements and using Fermat's Little Theorem and LaGrange's theorem. The conversation also discusses the importance of considering cases such as a^6, a^4, and a^36 in order to show that the order of an element must be a divisor of 108. The conversation also touches on the concept of quadratic residues and how they relate to primitive roots.

- #1

- 11

- 0

Physics news on Phys.org

- #2

- 1,059

- 1

You have to look at the multiplicative group = 108 elements. Then check out the factors.

- #3

- 11

- 0

- #4

- 11

- 0

It factors as 1 + 2^2*3^3 i know that

- #5

- 1,059

- 1

However, 0 is not included under multiplication, so there are only 108 elements. This comes under Fermat's Little Theorem: [tex]a^{p-1} \equiv 1 \bmod p. [/tex] In this case the prime is 109.

Now, while you may not understand group theory, I am going to quote a theorem of LaGrange: The order of the element divides the order of the group.

Which is this case means that an element either requires the power of 108 (primitative root) or it requires a divisor of that number.

Consider in the above we have the case that, the smallest power for a given a is 5, which does not divide 108, then [tex]a^5 \equiv 1 \bmod 108 [/tex] Well then since a^5 works, if we multiply this by 21, it should also work, and since 108 works then:

[tex]a^{105}\equiv a^{108} \equiv 1 Mod 109 [/tex], which after division tells that some element we thought required the power of five, need only be cubed to become 1. A contradiction. (Of course, this could be carried on further considering 2x5-3x3 =1.)

Now, while you may not understand group theory, I am going to quote a theorem of LaGrange: The order of the element divides the order of the group.

Which is this case means that an element either requires the power of 108 (primitative root) or it requires a divisor of that number.

Consider in the above we have the case that, the smallest power for a given a is 5, which does not divide 108, then [tex]a^5 \equiv 1 \bmod 108 [/tex] Well then since a^5 works, if we multiply this by 21, it should also work, and since 108 works then:

[tex]a^{105}\equiv a^{108} \equiv 1 Mod 109 [/tex], which after division tells that some element we thought required the power of five, need only be cubed to become 1. A contradiction. (Of course, this could be carried on further considering 2x5-3x3 =1.)

Last edited:

- #6

- 11

- 0

- #7

- 1,059

- 1

If we take a case like 5, which would not divide 108 and argue that this is the smallest power such that a becomes 1: [tex]a^5\equiv 1\bmod 109 [/tex] Then since its value is one, raising it to the 21st power should still give one. That gives then [tex]a^{105}\equiv 1\bmod 109 [/tex]

But, since we know in all cases a^108 is 1 modulo 109, we have [tex]a^{105}\equiv a^{108} \bmod 109 [/tex]

So dividing out by a^105 gives [tex]a^3\equiv 1 \bmod 109 [/tex], which gives a contradiction. In fact, carrying on in this way we could show that a^1 is congruent to 1 mod 109.

What is the reason for the above? To show that the order of the element (the smallest power to make 1) must be a divisor of 108. That no element, for example, is of order 5.

But, since we know in all cases a^108 is 1 modulo 109, we have [tex]a^{105}\equiv a^{108} \bmod 109 [/tex]

So dividing out by a^105 gives [tex]a^3\equiv 1 \bmod 109 [/tex], which gives a contradiction. In fact, carrying on in this way we could show that a^1 is congruent to 1 mod 109.

What is the reason for the above? To show that the order of the element (the smallest power to make 1) must be a divisor of 108. That no element, for example, is of order 5.

Last edited:

- #8

- 11

- 0

- #9

- 1,059

- 1

Jamesandthegi said:

- #10

- 11

- 0

- #11

- 1,059

- 1

Fortunately, there is a now a very simple answer. If we go ahead and count all the powers of a that contain 2, they can be eliminated, and similarly the powers of 3. But there is overlap,namely the powers of 6, which are counted twice. Carrying out these simple calculations will tell you along with counting the primitive roots, that 108 cases are accounted for.

- #12

- 11

- 0

- #13

- 1,059

- 1

If a^2 congruent to 1 Mod 108, then a^54 congruent to 1 Mod 108, yes.

What is important is that b^2 is congruent to a^54, or a^54 is a quadratic residue. Anything that is a quadratic residue will be congruent to 1 at the 54th power.

What is important is that b^2 is congruent to a^54, or a^54 is a quadratic residue. Anything that is a quadratic residue will be congruent to 1 at the 54th power.

Last edited:

- #14

- 11

- 0

- #15

- 1,059

- 1

I have used a in more than one way. However, a^54 is a quadratic residue because we have a b=a^27.

WHat I am using above is an "a" that is a primitative root. Then all the powers of a are different, some of which are primitative roots, but others are not. In any case an even power is a quadratic residue.

WHat I am using above is an "a" that is a primitative root. Then all the powers of a are different, some of which are primitative roots, but others are not. In any case an even power is a quadratic residue.

Last edited:

Share:

- Replies
- 13

- Views
- 177

- Replies
- 4

- Views
- 566

- Replies
- 13

- Views
- 734

- Replies
- 22

- Views
- 837

- Replies
- 17

- Views
- 1K

- Replies
- 9

- Views
- 657

- Replies
- 6

- Views
- 1K

- Replies
- 10

- Views
- 981

- Replies
- 3

- Views
- 1K

- Replies
- 4

- Views
- 934