Fermats little theorem on permutations

In summary, the conversation discusses the concept of a card shuffle and how it can be represented by a permutation. It is mentioned that it takes 52 perfect shuffles to get the deck of cards back in the original order and Fermat's Little Theorem is suggested as a way to prove this. The conversation also includes a hint to help with the proof, asking what k/2 (mod 53) is.
  • #1
lilcoley23@ho
19
0
I'm looking at a card shuffle. And in shuffle would be the permutation (1, 2, 3, ..., n, n+1, n+2, n+3, ...2n) to (2, 4, 6, ..., 2n 1, 3, 5, ...2n-1) I know that it would take 52 perfect shuffles to get the deck of cards back in the original order. I think that I'm supposed to show this using Fermats Little Theorem.
Fermats little theorem says a p-1 ≡ 1(mod p) or a p ≡ a(mod p). Now I'm pretty sure that using the permutation from above plugging in for Fermat'l Little Theorem looks like: 52 ≡ 2(mod 2n+1)
If that is right I'm not sure how to show that I came up with that 52.
Can somebody please help?
Thanks you so much! Nicole
 
Physics news on Phys.org
  • #2
lilcoley23@ho said:
… the permutation (1, 2, 3, ..., n, n+1, n+2, n+3, ...2n) to (2, 4, 6, ..., 2n 1, 3, 5, ...2n-1) …

Hi Nicole! :smile:

Hint: what is k/2 (mod 53)? :wink:
 

1. What is Fermat's Little Theorem?

Fermat's Little Theorem is a fundamental theorem in number theory that states that for any integer a and prime number p, ap ≡ a (mod p). In other words, the remainder when ap is divided by p is equal to a.

2. How does Fermat's Little Theorem relate to permutations?

Fermat's Little Theorem can be used to determine the number of permutations of a set, where the size of the set is a multiple of a prime number. This is because the number of distinct permutations of a set of n elements is n!, and n! is equivalent to np-1 (mod p) by Fermat's Little Theorem.

3. Can Fermat's Little Theorem be used to find the number of permutations of a non-prime size set?

No, Fermat's Little Theorem can only be used for sets whose size is a multiple of a prime number. For sets with non-prime sizes, other methods such as the Factorial Theorem must be used to determine the number of permutations.

4. Are there any exceptions to Fermat's Little Theorem?

Yes, there are some exceptions to Fermat's Little Theorem, known as Fermat pseudoprimes. These are composite numbers that satisfy the theorem for certain values of a. However, these exceptions are very rare and are difficult to find.

5. How is Fermat's Little Theorem used in cryptography?

Fermat's Little Theorem is used in the field of cryptography to ensure the security of encrypted messages. It is used in the RSA algorithm, where the theorem is used to choose large prime numbers that are used to generate public and private keys. It is also used in the Diffie-Hellman key exchange, which allows two parties to establish a shared secret key over an insecure channel.

Similar threads

Probability of Two Consecutive Same-Value Cards in a Shuffled Deck
    • Calculus and Beyond Homework Help
Replies
31
Views
3K
How to show that these sequences are summable?
    • Calculus and Beyond Homework Help
Replies
1
Views
255
MHB Exploring the Periodicity of Powers in Modular Arithmetic
    • Linear and Abstract Algebra
Replies
16
Views
4K
B What theorems are available when using modulo arithmetic?
    • General Math
Replies
11
Views
485
Comp Sci RSA system with p=17, q=11 and e=3. Find m corresponding to c=156
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
B Optimizing permutations of hero traits in a computer game
    • General Math
Replies
2
Views
675
MHB Fermat's Little Theorem .... Anderson and Feil, Theorem 8.7 .... ....
    • Linear and Abstract Algebra
Replies
2
Views
1K
I Fermat's Little Theorem .... Anderson and Feil, Theorem 8.7 .
    • Linear and Abstract Algebra
Replies
3
Views
2K
B How are permutations and probability related?
    • General Math
Replies
1
Views
1K
I Why prove Taylor's theorem with p(x)=q(x)−((b−a)^n/(b−x)^n)q(a)?
    • Calculus
Replies
9
Views
847

Hot Threads

Recent Insights

Back
Top