Question

Prove that \[x^{25}\equiv x\pmod {13}\].

Answer 1

\[x^{25}\equiv x\cdot(x^{12})^2 \equiv x\cdot(1)^2 \equiv x \pmod{13}\]

Answer 2

How do you know x is not divisible by 13?

Answer 3

Oh thats a mistake actually, good catch :)

Answer 4

Above line works when \(13\nmid x\)

Just add this for the case \(13 | x\) :
\(x^{25}\equiv 0 \equiv x \pmod{13} \)

Answer 5

......
I don't know what to say really......

Answer 6

when 13 | x, would you agree \(x\equiv 0 \pmod {13}\) ?

Answer 7

if you think about them, they both are equivalent statemetns

Answer 8

Let p be a prime and \(\gcd(a,p)=1\). Use Fermat's little theorem to show that \(x\equiv a^{p-2}b\pmod p\) is a solution to \(ax\equiv b \pmod p)\)

Answer 9

Am I suppose to say by Fermat's little theorem, \(a^{p-1}\equiv 1 \pmod p\) so \(a^{p-1}b\equiv b \pmod p\).

Answer 10

thats it! replace \(b\) by \(a^{p-1} b\) in the given congruence :
\[\large ax \equiv b \pmod{p}\]
\[\large ax \equiv a^{p-1}b \pmod{p}\]

divide \(a\) both sides

Answer 11

you're allowed to divide \(a\) both sides because \(\gcd(a, p)=1\)

Answer 12

Okay.

Prove that, if \(p\geq3\) is a prime then \(\sum_{k=1}^{p-1}k^p\equiv0\pmod p\).

Answer 13

Easy... use Fermat's little theorem for each term and add up

Answer 14

WHAT!?!?!?!?!?

Answer 15

since \(1\le k\le p-1\), we have \(\gcd(k, p)=1\) so \(k^p \equiv k \pmod{p}\) :

\[\sum_{k=1}^{p-1}k^p\equiv \sum_{k=1}^{p-1}k \pmod p \]

Answer 16

I am certainly thinking too complicated. I was thinking how to factorise the sum and prove that the factorisation is divisible by p lol.

Answer 17

Just believe that almost all the homework proofs are simple and short :)

Answer 18

It is IB past paper......

Answer 19

The difficulty is surreal yet I can't solve it.

Answer 20

I will close this question. I have an exam on discrete mathematics tomorrow and you saved my life.

Answer 21

I see you're fully ready for the exam! wish you all the best :)