- #1

Jamesandthegi

- 11

- 0

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

Jamesandthegi

- 11

- 0

Physics news on Phys.org

- #2

robert Ihnot

- 1,059

- 1

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

- #3

Jamesandthegi

- 11

- 0

- #4

Jamesandthegi

- 11

- 0

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

- #5

robert Ihnot

- 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

Jamesandthegi

- 11

- 0

- #7

robert Ihnot

- 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

Jamesandthegi

- 11

- 0

- #9

robert Ihnot

- 1,059

- 1

Jamesandthegi said:

- #10

Jamesandthegi

- 11

- 0

- #11

robert Ihnot

- 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

Jamesandthegi

- 11

- 0

- #13

robert Ihnot

- 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

Jamesandthegi

- 11

- 0

- #15

robert Ihnot

- 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:

Primitive roots are numbers that have a special property in modular arithmetic. They are important because they allow us to solve equations involving modular arithmetic and are used in various cryptographic algorithms.

The process of finding primitive roots can be complex and there is no general formula for finding them. One method is to exhaustively check all numbers less than the given modulus. Another method is to use the primitive root theorem, which states that if the modulus is of the form 2^{n}, 2^{n+1}, or 2^{n+2}, then 2 is a primitive root. There are also algorithms, such as the Shanks algorithm, that can be used to find primitive roots.

No, a number can only have one primitive root. This is because if a number has multiple primitive roots, then they must all have the same order, which is not possible since primitive roots must have different orders.

Primitive roots are used in various cryptographic algorithms, such as Diffie-Hellman key exchange and RSA encryption. In these algorithms, primitive roots are used to generate large numbers that are used as keys for encrypting and decrypting data. This is because primitive roots are difficult to predict and can help ensure the security of the encryption.

Primitive roots are necessary in modular arithmetic because they allow us to solve equations involving modular arithmetic and help us to find solutions to congruences. They also have applications in number theory and cryptography, making them an important concept in mathematics and computer science.

- Replies
- 3

- Views
- 1K

- Replies
- 5

- Views
- 1K

- Replies
- 4

- Views
- 3K

- Replies
- 1

- Views
- 2K

- Replies
- 1

- Views
- 1K

- Replies
- 8

- Views
- 5K

- Replies
- 2

- Views
- 1K

- Replies
- 1

- Views
- 1K

- Replies
- 1

- Views
- 2K

- Replies
- 5

- Views
- 8K

Share: