# Fermats little theorem on permutations

• lilcoley23@ho
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.
lilcoley23@ho
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.
Thanks you so much! Nicole

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!

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

## 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.

• Calculus and Beyond Homework Help
Replies
31
Views
3K
• Calculus and Beyond Homework Help
Replies
1
Views
364
• Linear and Abstract Algebra
Replies
16
Views
4K
• General Math
Replies
11
Views
586
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• General Math
Replies
2
Views
718
• Linear and Abstract Algebra
Replies
2
Views
1K
• Linear and Abstract Algebra
Replies
3
Views
2K
• General Math
Replies
1
Views
1K
• Calculus
Replies
9
Views
954