Jamesandthegi
- 11
- 0
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
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
14 replies · 2K views
Discussion
Physics news on Phys.org
robert Ihnot
- 1,057
- 1
You have to look at the multiplicative group = 108 elements. Then check out the factors.
Jamesandthegi
- 11
- 0
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?
Jamesandthegi
- 11
- 0
It factors as 1 + 2^2*3^3 i know that
robert Ihnot
- 1,057
- 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:
Jamesandthegi
- 11
- 0
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
robert Ihnot
- 1,057
- 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:
Jamesandthegi
- 11
- 0
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
robert Ihnot
- 1,057
- 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
Jamesandthegi
- 11
- 0
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
robert Ihnot
- 1,057
- 1
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.
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.
Jamesandthegi
- 11
- 0
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?
robert Ihnot
- 1,057
- 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:
Jamesandthegi
- 11
- 0
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
robert Ihnot
- 1,057
- 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: