• Jamesandthegi
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.
Jamesandthegi
Please prove that if x is quadratic nonResidue modulo 109 and x also cubic nonresidue modulo 109 than x is guaranteed to be primitive root modulo 109 thanks you very much

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

What is this gorup? This is a number theory question not a group question? Can you show it with the number theory ? What is this group?

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

However, 0 is not included under multiplication, so there are only 108 elements. This comes under Fermat's Little Theorem: $$a^{p-1} \equiv 1 \bmod p.$$ 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 $$a^5 \equiv 1 \bmod 108$$ Well then since a^5 works, if we multiply this by 21, it should also work, and since 108 works then:

$$a^{105}\equiv a^{108} \equiv 1 Mod 109$$, 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:
That seems like it has nothing to do with problem. where does 105 come in. No group,s no lagrange's it should be proven using number theory

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: $$a^5\equiv 1\bmod 109$$ Then since its value is one, raising it to the 21st power should still give one. That gives then $$a^{105}\equiv 1\bmod 109$$

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

So dividing out by a^105 gives $$a^3\equiv 1 \bmod 109$$, 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:
Well of course we know that it a divisor of 108, this is trivial fact no? It's not trivial to show that a^6 ~= 1 or a^4 ~= 1 or a^36 ~=1

You can call it a trival fact if you like, but look at the original question below:

Jamesandthegi said:
Please prove that if x is quadratic nonResidue modulo 109 and x also cubic nonresidue modulo 109 than x is guaranteed to be primitive root modulo 109 thanks you very much

Maybe you misunderstand? It is trivial that the order of a must divide phi(109). Great so then we have to consider the cases {a, a^2, a^3, a^4, a^6, a^9, a^12, a^18, a^36, a^54} only, I kniw that

You are correct! There is another aspect to this problem. Take a primitive root and consider all its powers: a, a^2, a^3...a^108 = 1. Now the powers of a that are relatively prime is phi(108) = 36. These are all primitive roots.

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.

i don't know how you can automatically say that. we kniw a^54 ~=1 by euler's criterion. so say a^2 = 1, then if you multiple out a^2 27 times you would get a^54 is 1 is rthat right?

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.

Last edited:
i do not get it. what is b? what i meants was say a^2 = 1 then a^2*a^2*...*a^2 = 1 but that' can not happen because we knows a^54 = -1 i don't see what the b is and we are not given a^54 is not a quad res just that a is

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.

Last edited:

## 1. What are primitive roots and why do they matter?

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.

## 2. How do I find primitive roots?

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 2n, 2n+1, or 2n+2, then 2 is a primitive root. There are also algorithms, such as the Shanks algorithm, that can be used to find primitive roots.

## 3. Can a number have more than one primitive root?

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.

## 4. How are primitive roots used in cryptography?

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.

## 5. Why do we need primitive roots in modular arithmetic?

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