• Support PF! Buy your school textbooks, materials and every day products Here!

Fermat's/Euler problem

  • Thread starter pacdude9
  • Start date
  • #1
4
0
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
308
0
for the first one, see if this helps...

By Fermat's Theorem (assuming that p and p are relatively prime...) we have
[tex]q^p=q [/tex]mod [tex]p [/tex]. We can cancel q from both sides since gcd(q,p) = 1, so [tex]q^{(p-1)} = 1 (mod p)[/tex]. Also [tex] p^{(q-1)} = 0 (mod p) [/tex] we get

[tex]p^{(q-1)} + q^{(p-1)} = 1 (mod p) [/tex]

can you go from there?
 
Last edited:

Related Threads on Fermat's/Euler problem

  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
7
Views
610
Replies
7
Views
888
  • Last Post
Replies
3
Views
13K
  • Last Post
Replies
8
Views
1K
Replies
4
Views
3K
Top