Let $n \in \mathbb{N}$ and suppose that $n = kl$, for some $k, l \in \mathbb{N}$ such that $1&lt;k&lt;l&lt;n$. Show that $(n-1)! \equiv 0(\mod n)$. So far I have show Wilson's Theorem, that is $(p-1)! \equiv -1(\mod p)$ for some prime $p$. How would I go about this?
9242
I have a proof and need some feedback. It seems really obvious that the statement is true but it is always the obvious ones that are a little trickier to prove. So I would appreciate any feedback. Thank you!  Here is what I am asked to prove:     If $n$ is composite then $(n-1)! \equiv 0 \pmod n$.   Proof:  $n$ is composite $\implies n=ab$ where $a,b \in \mathbb{Z}$ and $0&lt;a,b&lt;n$.  Case 1: If $a=b$ then $n=a^{2}$. Now $n \mid (n-1)! \implies a \mid (n-1)!$, so $$\begin{aligned} (n-1)! &amp;\equiv 1\times 2\times \dotsb \times a \times\dotsb\times (n-a)\times\dotsb\times (n-1) \\ &amp;\equiv 1\times 2\times \dotsb\times a \times\dotsb\times -a\times\dotsb\times -1 \\ &amp;\equiv 0 \pmod n \end{aligned}$$  Case 2: $0&lt;a&lt;b&lt;n$.  Then, since $a \mid n$, $b \mid n$ and $n \mid (n-1)!$ we have that $a \mid (n-1)!$ and $b \mid (n-1)!$.  So this implies $(n-1)! \equiv 1\times 2\times \dotsb\times a \times\dotsb\times b\times\dotsb\times (n-1) \equiv 0 \pmod n$, Q.E.D.
11214
Attempted Proof:  Let $S = \{k: n^k-1 \equiv 0 \pmod{p}, k\in \mathbb{N}\}$. Minimal element $r$ exists by Well-Ordering. we show $r=q$.  We note, $\gcd(p,n)=1$, otherwise $p \mid n^q-1 \implies p \mid 1$.  We have:  $n \not\equiv 1 \pmod{p}\implies n^2 \not\equiv n \pmod{p}$ ; [since $p , n$ are coprime and  $p$ prime ]. Now, for any $0&lt;j&lt; i &lt; r,$  $n^i \equiv n^j \pmod{p} \implies n^j(n^{i-j}-1) \equiv 0 \pmod{p} \implies (n^{i-j}-1) \equiv 0 \pmod{p} $, contradicting the minimality of $r$.   Now, we proceed to show that, all elements of $S$ are integral multiples of $r$. (Claim 1)  We have, $n^{tr} \equiv 1 \pmod{p} \implies n^{tr+l} \equiv n^l \pmod{p} $, for $0\leq l &lt;r$. Now, for any two such $l$, say $c$ and $d$, with $d&lt;c$ ,   $n^{tr+c} \equiv n^{tr+d} \pmod{p} \implies n^{tr+d}(n^{c-d}-1) \equiv 0 \pmod{p}$, which again contradicts our assumption that $r$ is the least element of $S$. Hence, Claim 1 is established. But, it implies that $q$ is composite (an impossibility); hence $r$ must be equal to $q$ .   Finally, by Fermat's Little Theorem, we have $n^{p-1} \equiv 1 \pmod{p}$ [ it holds, since $\gcd (p, n) =1$].   Therefore, $p-1$ must be an integral multiple of $q$, i.e. $q \mid p-1$.   PS: I am aware of the duplicates, but I want my solution checked. Thank you.
51735
I'm having difficult proving this.  As a hint the exercise to prove first, that if $a\lneqq \pm 1$ satisfies $a \equiv 3 \pmod4$, then exist $p$ prime, $p \equiv 3 \pmod 4$ such $p\mid4$. But I'm not really getting for what purpose can this be used.
95686
Let $p$ be a prime number. If -1 is a square in $\mathbf F_p$, it means that there exists an element of order 4. So $p-1$ is divisible by 4 and therefore $p \equiv 1$ (mod 4). I wonder the converse is also true. Does $p \equiv 1$ (mod 4) mean the existence of an element whose square is $-1$ in $\mathbf F_p$?
13594
Can $n!$ be a perfect square when $n$ is an integer greater than $1$?  Clearly, when $n$ is prime, $n!$ is not a perfect square because the exponent of $n$ in $n!$ is $1$.  The same goes when $n-1$ is prime, by considering the exponent of $n-1$. What is the answer for a general value of $n$?  (And is it possible, to prove without Bertrand's postulate. Because Bertrands postulate is quite a strong result.)
4827
I came across this problem and I believe Lagrange's theorem is the key to its solution.  The question is:     Let $p$ be an odd prime. Prove that there is some integer $x$ such that $x^2 \equiv −1 \pmod p$ if and only if $p \equiv 1 \pmod 4$.   I appreciate any help.  Thanks.
38732
Prove that $$\frac{(n+1)(n)^2(n-1)^2...(n-k+2)^2(n-k+1)}{(k+1)(k)^2(k-1)^2...(2)^2(1)}$$ is or is not an integer for $0\leq k \leq n$, where $k$ and $n$ are integer values. This looks like $\frac{(n+1)!(n)!}{(n-k+1)(n-k)(k+1)!(k)!}$. The above statement is true for k=1 and k=2 as seen by observing modular residues. Not sure how to proceed.
36335
I need to show that if $(n-2)! \equiv 1 \pmod n$ then $n$ is prime. I think that if $n$ is composite, then we'll have every factor of $n$ in $(n-2)!$, and it would yield that $(n-2)! \equiv 0 \pmod n$. However, I didn't use the fact that it specifically congruent to $1 \bmod n$, so I think I'm getting something fundamental wrong. Is my solution correct? Why do we demand congruence to $1 \bmod n$?
26617
Let $n = 712! + 1$ If $n$ was a prime number then, by Wilson's theorem:  $ (712!)! \equiv -1 \pmod{712}$  The double factorial makes it seriously more difficult...  But We can require:  $$712!! + 1 \equiv 0 \pmod{712}$$  $$712 = 2\cdot 356$$   Hence: $712!! = 2^{356} 356!$  Lets compute: $356! \pmod{712}$. Obviously:  $$356! = (356 \cdot 2) \cdot (355!/2)  = 712 \cdot 355!/2$$  Then: $356! \pmod{712} \equiv 0$.   Now, $2^{356} \pmod{712}$  $2^{356} = 2^{6 + 350}$  Nevermind, what should I do?
72318
I have not been able to solve this problem. Any insights would be appreciated!   Let $x, n > 1$ be integers. Suppose that for each $k > 1$ there exists an integer $a_{k}$ such that $x − a_k^n$ is divisible by $k$. Prove that $x = A^{n}$ for some integer $A$.
43674
Calculate for every positive integer $n$ and for every prime $p$ the expression  $$1^n +2^n + \cdots +(p-1)^n \mod p$$    I need your help for this. I don't know what to do, but I'll show you what I know.   Wilson's theorem The identity $X^p-X = \prod_{a \in \mathbb{F}_p-1}(X-a)$ $\exists a \in \mathbb{Z}, \ a^2 \equiv -1 \mod p \qquad \iff \qquad p \equiv 1 \mod 4$   Now can you please provide me a hint?
59439
Is there any way of determining if $\binom{n}{k} \equiv 0\pmod{n}$.  Note that I am aware of the case when $n =p$ a prime.  Other than that there does not seem to be any sort of pattern (I checked up to $n=50$).  Are there any known special cases where the problem becomes easier?  As a place to start I was thinking of using $e_p(n!)$ defined as:  $$e_p(n!) = \sum_{k=1}^{\infty}\left \lfloor\frac{n}{p^k}\right \rfloor$$  Which counts the exponent of $p$ in $n!$ (Legendre's theorem I believe?)  Then knowing the prime factorization of $n$ perhaps we can determine if these primes appear more times in the numerator of $\binom{n}{k}$ than the denominator.  Essentially I am looking to see if this method has any traction to it and what other types of research have been done on this problem (along with any proofs of results) before.  Thanks!
9380
Is the following conjecture true?     Given an $n&gt;1$ and a $k$ such that $0&lt;k&lt;n$ then $\gcd\left(\binom{n}{k}, n\right)&gt;1$   This was a question asked in my old Number Theory course that I recently remembered. It was posed after we learned that $p\mid\binom{p}{k}$ for $0&lt;k&lt;p$. We never resolved it either way. I expect it to be true and have an elegant answer, but I haven't been able to prove it.
27829
I've been messing around with modular arithmetic recently, and stumbled across this, but couldn't find a proof for it anywhere. I hate taking things as truth without knowing why, so could anyone provide a (fairly simple) proof?
30096
Verify that $4(29!)+5!$ is divisible by $31$  I know I have to use Wilsons theorem: $(p-1)!=-1\pmod p$ but I'm not really sure how to apply this theorem. Step by step explanation please? Thank you!
104354
I first noticed this is true for the integers of the sequence $9, 99, 999, 9999,\dots$, since for some term $a_n=10^n-1$ in the sequence and $p$ a prime other than $2$ or $5$, we have $a_n\equiv 0 (mod\ p)\Leftrightarrow 10^n\equiv 1 (mod\ p)$ and we can find infinitely many $n=k(p-1)$ so that $10^n=(10^{p-1})^k\equiv 1^k\equiv 1 (mod\ p)$ by Fermat's little theorem.   I'm curious, is there a similar way to show this is true for repunits $1, 11, 111,\dots$?
49380
How can I show that $n^2&lt;n!$ for all $n\geq 4$ Step 1 For $n=1$, the LHS=$4^2=16$ and RHS=$4!=24$. So LHS$&lt;$ RHS. Step 2 Suppose the result be true for $n=k$  i.e., $k^2&lt;k!$ Step 3 For $n=k+1$ $(k+1)^2=k^2+2k+1$ What will be the next step?