- #1

- 26

- 0

As the title says, for any a>1 and n>0

- Thread starter xax
- Start date

- #1

- 26

- 0

As the title says, for any a>1 and n>0

- #2

- 1,056

- 0

Set [tex] a^n=1+M[/tex]. Consequently [tex]a^n\equiv 1ModM[/tex] and is the smallest n for a>1, n>0. It also follows from the last equation that a belongs to the reduced residue group of order [tex]\phi{M}[/tex]. Consequently by LaGrange's Theorem, n is a divisor of the order of the group.

Last edited:

- #3

- 261

- 0

You cannot say that for sure, or I am wrong?Set [tex] a^n=1+M[/tex]. Consequently [tex]a^n\equiv 1ModM[/tex] and is the smallest n for a>1, n>0. It also follows from the last equation that a belongs to the reduced residue group of order [tex]\phi{M}[/tex]. Consequently by LaGrange's Theorem, n is a divisor of the order of the group.

- #4

- 1,056

- 0

al-mahed: You cannot say that for sure, or I am wrong?

I can say what I meant for sure. However, the way I wrote it, "And is the smallest n for a>1,

n>0, which you have put in red, this, I see, is confusing. It is not what I am asserting, but is repeating the conditions given by xax, "As the title says, for any a>1 and n>0."

So that since n >0, and a>1, which is a very minimal restriction, we know we have a positive value here which I deliberately set: [tex] a^n=1+M[/tex] This is the smallest value of n which can be used to achieve the required non-trivial equation: [tex]a^n\equiv 1ModM[/tex] since the left side is, in fact, just 1 more than M.

Thanks for the comment, it shows someone is reading this.

I can say what I meant for sure. However, the way I wrote it, "And is the smallest n for a>1,

n>0, which you have put in red, this, I see, is confusing. It is not what I am asserting, but is repeating the conditions given by xax, "As the title says, for any a>1 and n>0."

So that since n >0, and a>1, which is a very minimal restriction, we know we have a positive value here which I deliberately set: [tex] a^n=1+M[/tex] This is the smallest value of n which can be used to achieve the required non-trivial equation: [tex]a^n\equiv 1ModM[/tex] since the left side is, in fact, just 1 more than M.

Thanks for the comment, it shows someone is reading this.

Last edited:

- #5

- 26

- 0

I understood why [tex] a^n=1+M[/tex], but did not understand why M=n.

Thanks

- #6

- 1,056

- 0

- #7

- 26

- 0

you've saved me again robert, thanks.

- #8

- 1,056

- 0

What you have to do sometimes is look at problems. Say, 2^4 =16. So we set the modulus at 15. Thus we have 2^4 ==1 Mod 15.

Now phi(15)= phi(5)*phi(3) = 4x2 = 8. That means that the reduced residue group of elements relatively prime to 15 are 8 in number. They are the elements that form the multiplicative group. (3 for example is not in this group since there is no solution to 3X==1 Mod 15. So 3 has no inverse.)

In fact, the eight elements are: 1, 2, 4, 7, 8, 11, 13, 14. Each one of these group elements has an inverse. For example: 1*1==1 Mod 15, 2*8=16==1 Mod 15, 4*4==1 Mod 15, 7*13 = 91==1 Mod 15, and so forth.

The theorem then states that the order of the element, which is 4, divides the order of the group which is 8.

Now phi(15)= phi(5)*phi(3) = 4x2 = 8. That means that the reduced residue group of elements relatively prime to 15 are 8 in number. They are the elements that form the multiplicative group. (3 for example is not in this group since there is no solution to 3X==1 Mod 15. So 3 has no inverse.)

In fact, the eight elements are: 1, 2, 4, 7, 8, 11, 13, 14. Each one of these group elements has an inverse. For example: 1*1==1 Mod 15, 2*8=16==1 Mod 15, 4*4==1 Mod 15, 7*13 = 91==1 Mod 15, and so forth.

The theorem then states that the order of the element, which is 4, divides the order of the group which is 8.

Last edited:

- Replies
- 2

- Views
- 2K

- Last Post

- Replies
- 7

- Views
- 8K

- Replies
- 11

- Views
- 24K

- Replies
- 6

- Views
- 22K

- Last Post

- Replies
- 33

- Views
- 10K

- Last Post

- Replies
- 12

- Views
- 7K

- Last Post

- Replies
- 7

- Views
- 4K

- Last Post

- Replies
- 10

- Views
- 6K

- Last Post

- Replies
- 13

- Views
- 2K

- Replies
- 13

- Views
- 15K