I'm currently working in the following Wilson's theorem excercise:  Being $p$ an odd prime. Let $x=((p-1)/2)!$ Using the fact that $(p − 1)! = (1(p − 1)) (2(p − 2)) · · · (((p − 1)/2)((p + 1)/2))$ show that: $$-1 \equiv (-1)^{(p-1)/2}x^2 \pmod p$$  I'm starting from: $$(1(p − 1)) (2(p − 2)) · · · (((p − 1)/2)((p + 1)/2))\equiv -1 \pmod p$$ My plan is to simplify terms on the left side to reach that $(p-1)/2$ which is the power of that $-1$, but I really don't know how can it be raised to that power, any hint or help will be really appreciated.
1749
Suppose that $p$ is a prime. Suppose further that $h$ and $k$ are non-negative integers such that $h + k = p − 1$.   I want to prove that $h!k! + (−1)^h \equiv 0 \pmod{p}$  My first thought is that by Wilson's theorem, $(p-1)! \equiv -1 \pmod{p}$, and $h!k!$ divides $(p-1)!$ (definition of a binomial). Where would I go from here?
94191
Suppose that p ≡ 3 (mod 4)   and $r = \frac {p-1}2$  Show that $r! \equiv (−1)^k \pmod p$  where k is the number of non-quadratic residues modulo p which are smaller than $\frac p2$  I know from Wilson's Theorem for a prime p:  $(p−1)! \equiv −1 \pmod p$  I don't know where to start from ..   I managed to show that   $r! \equiv \pm 1 \pmod p$  any help or hint will be appreciated
34003
Are there any solutions to $x^{n}-1=p$ with p prime, integers $x,n&gt;1$ and $x$ not a power of $2$?  $x$ must be even. $n$ is odd since if $n=2m$ then $p=x^{n}-1=(x^{m}+1)(x^{m}-1)$ hence $p=x^{m}+1$ and $1=x^{m}-1$, which has solution $p=3$ given by $x=2^{2}$.   This generalises; for any solution to $x^{n}-c^{2}=p$, $n$ must be odd. And for any solution to $x^{n}-c=p$, $x$ is odd iff $c$ is odd unless $p=2$ and, if $a$ divides $c$ and $p$ does not divide $c$ then $x$ divides $c$.
71274
I am really having trouble working a problem in my course. I will post it and then add what I have thought etc.  Let p be an odd prime, then using the Euclidian Algorithm, calculated the GCD of of $x^{p-1}-1$ and $x^2+1$ in $\mathbb{Z} / p\mathbb{Z}[x]$  Also, how does $p=1 (mod4)$ tell us that  $-1$ is a square in $\mathbb{Z} / p\mathbb{Z}$, infact that $-1$ is a square here if and only if $p=1(mod4)$.  My thoughts:   I know that $$x^{p}-x=(x)(x-1)(x-2)…(x-(p-1))$$ and so that in this sense our roots will be the congruence classes of $1,2,…p-1$  and also that $$x^{p-1}-1=(x-1)(x-2)…(x-(p-1))$$  But I get lost when trying to apply the EA to these polynomials,  like how can I do it when p is arbitrary?  Preferably id like to be able to understand/see how to do the first part first i.e. using division with residue and then move on to the second part. Any insight/hint or solution to this would be great,  Thank you all  Update:  When I try to do division with residue, I just get  $$x^{p-1}-1=(x^2+1)(x^{p-3}-x^{p-5}+x^{p-7}-x^{p-9}...)$$  for example,  $p=7$  $$(x^{6}-1)=(x^2+1)(x^4-x^2+1)$$  for $p=11$  $$(x^{10}-1)=(x^2+1)(x^{8}-x^{6}+x^{4}-x^{2}+1)$$  which for specific cases tells me that 1 is the gcd, but I dont know how to generalize that for the case with arbitrary prime p.
18060
let q be an odd prime and p a prime dividing $1+n+\dots+n^{q-1}$. Prove that $p = 1 \mod q$ or $p = q$.  I don't actually know how to start, i thought of using fermat's little theorem or an application of eulers formula, but it didn't really give me any insights.   Any hints?
20207
The Wiki page on  says     The pair $(m, m+2)$ is twin prime, iff $4((m-1)! + 1) \equiv -m \pmod {m(m+2)}$.   This is obviously connected to Wilson's Theorem. Can anybody provide a proof for that, along the lines of thought given here, ?
114259
Well, I wrote up a solution on it, but according to the place I found the problem, it isn't quite correct. Ah, I'm simply hoping someone will point out where I got wrong.  Now, let, $n^4+4^n = p^k$, where $p$ is an odd prime and $k$ is a positive integer.  Further, $p^k \equiv 1 \pmod 2$. Therefore, $n^4 + 4^n \equiv n^4 \equiv 1 \pmod 2$, and so $n \equiv 1 \pmod 2$. $n$ must be odd.  Okay, now let, $n = 2m +1$. Substituting it in $n^4+4^n$ and using the Sophie Germain inequality, we have,  $$n^4+4\cdot4^{2m} = n^4 + 4(2^m)^4 = (n^2 + 2^n+2^{m+1}\,n)(n^2 + 2^n-2^{m+1}\,n) = p^k$$  Now, as $p^k$ can only be factorized into smaller powers of $p$, let $n^2 + 2^n+2^{m+1}\,n = p^i$, and let $n^2 + 2^n-2^{m+1}\,n = p^j$ where $i+j= k$, obviously, and $i&gt;j$.  Now consider this:  $$\begin{align} p^i - p^j &amp; \equiv 0\\ 2\cdot2^{m+1}\,n = 2^{m+2}\,n &amp;\equiv 0 \pmod p \end{align}$$  But, as $p$ is odd, $\gcd(p, 2) = 1$, so $n \equiv 0 \pmod p$.  Now look at this:  $$\begin{align} p^i + p^j &amp;\equiv 0 \\ 2(n^2 + 2^n) &amp;\equiv 0 \\ n^2 + 2^n &amp;\equiv 0 \pmod p \end{align}$$  But we just established that $n \equiv 0 \pmod p$, so $2^n \equiv 0 \pmod p$.  Therefore, let $2^n = jp$ for some integer $j$.  Now, $2^n$ is its own prime factorization, which is unique according to the Fundamental Theorem of Arithmetic and does not include $p$. Therefore, the above statement is an impossibility! There exist no such $p$ and $n$, and no odd prime powers can be written as $n^4+4^n$.  Ah, well, that's it. Sorry for the tediousness of it. I've still no clue how to use $\LaTeX$.  Thank you everybody,  Cheers.
22046
I got a question to show that :      If $p$ is prime number, then   $$x^p - x \equiv x(x-1)(x-2)(x-3)\cdots (x -(p-1))\,\,\text{(mod }\,p\text{)}$$    Now I got 2 steps to show that the two polynomials are congruent:   Show they have same roots. Show the leading term's coefficients on both sides are the same.    For step 2, I know it is obvious $x^p$ has coefficient 1 on both sides.  For step 1, but I am not sure how to find all the solutions for $x^p -x$ modulo $p$.
60492
If $2^n+1$ is prime how to show that  $n$ must be a power of $2$  Being at elementary level I am at a loss what to begin with?
62474
I want to prove that if $p$ is a prime and $x,y \in \mathbb{Z}$, then $$(x+y)^p \equiv x^p+y^p \pmod{p}$$  So far I know that $$(x+y)^p = \sum_{k=0}^{p} \dbinom{p}k x^{p-k} y^k$$  A part of the above equation is supposed to cancel, I think, but I can't figure out a way how to make it cancel.
94198
Find the remainder when $45!$ is divided by $47$?  My approach I am using Wilson's theorem to solve the problem. I reduced the expression into ($47$-$1$-$1$)!/$47!$=$(47$-$1$)/$47$!-$1$/$47!$=-$1$-$1$=-$2$  Am I right in my approach.Please correct me if I am wrong? Please correct me how to approach towards the problem.
25177
Assume: $p$ is a prime that satisfies $p \equiv 3 \pmod 4$  Show: $x^{2} \equiv -1 \pmod p$ has no solutions $\forall x \in \mathbb{Z}$.  I know this problem has something to do with Fermat's Little Theorem, that $a^{p-1} \equiv 1\pmod p$. I tried to do a proof by contradiction, assuming the conclusion and showing some contradiction but just ran into a wall. Any help would be greatly appreciated.
68761
I found the following question and can't make much headway with it.  Show that there exist infinitely many positive integers $n$ such that $2^n \equiv n \mod p$ where $p$ is a odd prime...  I started by writing the number as $n=(p-1)k+c$ which implies $$2^c \equiv c-k \mod p$$ where I used Fermat's Little theorem. Now if $k$ is of the form $pm$ for some integer $m$ we get $n=(p-1)(p)m+c$   $$2^c \equiv c \mod p$$ and we have reduced $n$ to some smaller integer $c$ but I can't figure out how to find the smallest number $c$ which would then generate infinitely many $n$.  Any help in finding a possible approach to this would be highly appreciated.
116517
Given a prime $p$ and a natural number $k$, such that $k$ is not divisible by $p - 1$, prove that $\sum_{i = 1}^{p - 1}i^k \equiv 0 \pmod p$.  I split the proof into two cases: one where $k$ is odd and another where it is even.  The case where $k$ is odd can be proven as follows:  $$\sum_{i = 1}^{p - 1}i^k \equiv \sum_{i = 1}^{\frac{p - 1}{2}}i^k + \sum_{i = 1}^{\frac{p - 1}{2}}(-i)^k \pmod p$$  Since $k$ is odd each $(-i)^k = -i^k$, and will cancel with the positive $i$ leaving a zero. Therefore,   $$\sum_{i = 1}^{p - 1}i^k \equiv 0 \pmod p \text{ if $k$ is odd.} $$   I approached the case where $k$ is even in a similar fashion.   $$\sum_{i = 1}^{p - 1}i^k \equiv \sum_{i = 1}^{\frac{p - 1}{2}}i^k + \sum_{i = 1}^{\frac{p - 1}{2}}(-i)^k \equiv 2(\sum_{i = 1}^{\frac{p - 1}{2}}i^k) \space \pmod p$$  Since $p$ is prime, we just need to prove that $\displaystyle\sum_{i = 1}^{\frac{p - 1}{2}}i^k \equiv 0 \pmod p$.  I was stumped after this, so I considered a counterexample, one where $k$ is divisible by $p - 1$. In that I considered a case where $p = 5, k = 8$:  $$1^8 + 2^8 + 3^8 + 4^8 \equiv 1 + 1 + 1 + 1 \space \pmod p$$  This and a few other cases led to the conjecture that all the numbers below $p$ have a mod cycle $(mod \space p)$ that is divisible by $p - 1$. I tested it with $p = 7$.  $2: 2, 4, {\color{red}1}$  $3: 3, 2, 6, 4, 5, {\color{red}1}$  $4: 4, 2, {\color{red}1}$  $5: 5, 4, 6, 2, 3, {\color{red}1}$    After this I was stuck. I couldn't see how this would help me solve the problem. And, more importantly, I couldn't prove my conjecture.
81606
I have come across this question, which reminded me of Fermats little theorem, i dont know if the Fermats theorem is actually in use in the following mathematical statements   an integer a is a coprime with p and a coprime with q (p and q are different prime numbers )then prove that  $$a^{(p-1)(q-1)} \equiv 1(\operatorname{mod} pq) $$  $$p^{q-1}+q^{p-1} \equiv 1(\operatorname{mod} pq)$$  any help would be appreciated, thanks in advance.
120574
So I have seen the similar question and answers on here for $x^4 +1$, but I am having trouble extending anything there to this polynomial... I understand it is fairly trivial with Galois theory, but my class has just barely covered Field Extensions, so suffice it to say we have no Galois theory to play with.  I managed to prove it for the primes such that $p \equiv 1, 7 \pmod 8$, by noting that $2$ is a square modulo those primes and thus $x^4 - 2x^2 +1 = (x^2 -1 + 2qx)(x^2 - 1 - 2qx)$ for those $\mathbb{Z}_p$... however, trying to get a similar result for $3 \pmod 8$ and $5 \pmod 8$ has been stumping me for a long time, I am having a hard time making $q^2 = -1$ and $q^2 = -2$ give me something factorable...  I guess the worst part of all of this is that I don't think this solution is even particularly enlightening, in terms of abstract algebra. It's really just some number theory trickery. I don't think my course has prepared me theoretically for this problem, does anyone have an elementary approach to it?
124268
Given a prime $p$ and number $a$, how do I find the smallest $n$ such that $n^a\equiv 1 \pmod p$? Is there a non trial-and-error method?  Edit: obviously removing $n=1$!