Expansion of Fermat's Little Theorem

  • Thread starter pacdude9
  • Start date
  • #1
4
0

Main Question or Discussion Point

I've got a pair of (related) problems that are keeping me stumped. The two problems they are asking me to prove are:

[tex] p^{(q-1)} + q^{(p - 1)} \equiv 1 \; (\!\!\!\!\!\! \mod \, pq) [/tex]

[tex]a^{\phi(b)} + b^{\phi(a)} \equiv 1
\; (\!\!\!\!\!\! \mod \, ab)[/tex]

Where [tex] \phi(n) [/tex] is Euler's Totient Function.

I know that these are similar, as the second problem is using Euler's Theorem, a generalization of Fermat's Little Theorem, I just can't seem to figure them out.
 

Answers and Replies

  • #2
430
3
Can you show:
[tex]p^{q-1}+q^{p-1}\equiv 1 \pmod{p}[/tex]
? If so can you do the same mod q and combine these results to get it mod pq?
 
  • #3
430
3
BTW you are probably forgetting some requirements, because as stated your identities are false. Take for instance a=4, b=6, then you get:
[tex]\phi(a)=\phi(b)=2[/tex]
[tex]a^{\phi(a)}+b^{\phi(b)}=4^2+6^2=52 \equiv 4 \pmod {ab=24}[/tex]
Perhaps you meant for a and b to be relatively prime. And in the first you can take p=q=2 and get:
[tex]p^{q-1}+q^{p-1} = 2^1+2^1 = 4 \equiv 0 \pmod {pq=4}[/tex]
Maybe p and q should be distinct?
 
  • #4
4
0
Perhaps you meant for a and b to be relatively prime.
Maybe p and q should be distinct?
Thanks! Yes, in the first one, p and q are distinct primes, and in the second, a and b are coprime.
 
  • #5
IB1
24
0
Indeed, Euler's Totient Function is a very nice generalization of Fermat's Little Theorem. There is an intuitive proof for both which is studied in "Olympiad Training" but if you're a student, you may try to use group properties. (hint- consider the set {1,2,...,p-1} and the multiplication modulo p. This is clearly a group. Then, What is the order of this group ? What is the order of each element? What does Lagrange's theorem implies ? Try first with Fermat's Little Theorem, and then you may try to expand in Euler's function)
 

Related Threads on Expansion of Fermat's Little Theorem

  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
5
Views
10K
  • Last Post
Replies
7
Views
6K
Replies
1
Views
2K
Replies
3
Views
1K
  • Last Post
Replies
2
Views
6K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
3K
  • Last Post
3
Replies
52
Views
10K
  • Last Post
Replies
9
Views
4K
Top