The question is to prove the following:     If $n&gt;4$ is composite, then $(n-1)! \equiv 0 \pmod n$   My attempt to prove so is the following:     Since $n$ is not prime, the prime factors of $n$ lies in $(n-1)!$ yielding a term of $kn$ for some integer $k$. Hence, it is divisible by $n$ as desired.   The proof seems too short, did I prove it correctly?
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.
114463
Question 1 Is the following proof of the infinitude of primes $\equiv 1\mod 4$ okay?  Consider a prime divisor $p\mid (n!)^2+1$. Then $(n!)^2\equiv -1 \mod p$, hence $n!$ has multiplicative order $4$ in $\Bbb F_p^\times$ (question: is this conclusion true? what did I use here?).  Thus $n!\in \Bbb F_p^\times$ generates a subgroup of order $4$ and by Lagrange, $4\mid p-1$, i.e. $p\equiv 1\mod 4$.  Now we do the same thing, replacing $n$ by $p$. This will give a new prime $\equiv 1\mod 4$ and this prime is bigger than $p$ (otherwise it would divide $1$).  Question 2 My lecture notes say that from this one can conclude that there are infinitely many primes $p\equiv 3\mod 4$ by considering $n!-1$, which leaves remainder $3$ upon division by $4$. How does this imply infinitude of such primes?
19148
Why is it that $\forall n \in N$, $2^n$ is not divisible by $3$?  I can prove it easily by induction, but I don't understand the intuition of why this is true. Could anyone please supply the intuition? [This has been answered.]  Moreover, I understand that there's also a proof of this fact that uses modular arithmetic. How does this proof go? [Also answered - it follows immediately from the definition of the modulus operation.]
855
If $n&gt;1$ is an integer, then $\sum \limits_{k=1}^n \frac1k$ is not an integer.  If you know , then you know there must be a prime $p$ between $n/2$ and $n$, so $\frac 1p$ appears in the sum, but $\frac{1}{2p}$ does not. Aside from $\frac 1p$, every other term $\frac 1k$ has $k$ divisible only by primes smaller than $p$. We can combine all those terms to get $\sum_{k=1}^n\frac 1k = \frac 1p + \frac ab$, where $b$ is not divisible by $p$. If this were an integer, then (multiplying by $b$) $\frac bp +a$ would also be an integer, which it isn't since $b$ isn't divisible by $p$.  Does anybody know an elementary proof of this which doesn't rely on Bertrand's Postulate? For a while, I was convinced I'd seen one, but now I'm starting to suspect whatever argument I saw was wrong.
43536
Can you prove that if $p$ is a prime greater than $5$, then the sum of the squares of the quadratic nonresidues modulo $p$ is divisible by $p$?  Note that I have just proved that the sum of the quadratic residues modulo $p$ is divisible by $p$ for $p$ greater than $3$.
112475
I am trying to prove that ($\forall \ n\in\mathbb{N}$) there exists a prime number $q$ such that $n &lt; q \le 1 + n!$  I have made a graph with $n=0$ through $n=10$ and found solutions to all of them looking for a pattern and I see that $n!$ gets enormous fast and it becomes quite obvious that there is a prime number in between them.    I have considered trying to prove by contradiction that $q$ does not exist on that interval, but I don't know where to go from that statement.  Could anybody help me figure it out?  I have been staring at it for hours and I can't figure out where to go.  Thank you.
73489
I know how to prove the fact that $ p$ | ${ p \choose k } $ (when writing it as a fraction, $p$ cannot be divided by any of the $1\times2\times...\times k$ or $1\times2\times...\times(p-k)$ because $p$ is prime).  When I try to apply the same rationale for $ p$ | ${ p^n \choose k } $ I get stumped because $p^n$ is in fact divisible by one of the $k! = 1\times2\times...\times k$, where $0 &lt; k &lt; p^n$.  If we take the example of $2^3$ and $k = 7$, we can easily see that $k! = 1 \times 2 \times ... \times 6 \times 7$, and $2$ clearly divides $2^3$.  How else can I approach this?
81966
I have been stuck on this one for months, really simple to state, really giving me trouble.     Show that if $m^4 + 4^n$ is prime, $m&gt;0$, $n&gt;0$, then $m$ is odd and $n$ is even, except when $m=n=1$.   The case $m=n=1$ gives $5$, so that is why it is excluded. Clearly $m$ is odd, for if it was even, the number would be divisible by at least $4$, but I can't seem to get rid of the case where $n$ must be odd.   The only thing I've managed to try is to write $m$ as an odd number, say $m = 2k+1$, and $n = 2\ell + 1$, then get $$ m^4 + 4^n = (2k+1)^4 + 4^{2\ell+1} = 16k^4 + 32k^3 + 24k^2 + 8k + 1 + 4^{2 \ell + 1} $$ and this is congruent to $0 \mod 5$ unless $k \equiv 2 \mod 5$, and now it gives you an even more ugly polynomial if I write $k = 5j+2$, and it's not working. I've tried other inconclusive approaches, like trying to see if two numbers of some form generate numbers of the same form.. (for instance primes of the form 8k+1 and 8k+7 always generate primes of the same form when multiplied together, stuff like that).  Any ideas? Even just ideas you haven't gave a thought... they're welcome!
35299
Proof that if $p$ is a prime odd and $k$ is a integer such that $1≤k≤p-1$ , then the binomial coefficient  $$\displaystyle \binom{p-1}{k}\equiv (-1)^k \mod p$$  This exercise was on a test and I could not do!!
38892
$(n!+1,(n+1)!)$ can be rewritten as $(n!+1,(n+1)*n!)$.  I know that if $n!$ is divisible by a prime $p$ then $p$ doesn't divide n!+1. So when I'm looking at then is $(n!+1 , n+1)$ which I can make $(n!-n,n+1)$ by  subtracting $n+1$ from $n!+1$ and since gcd is preserved in linear combinations I  still get the same gcd for $(n!-n,n+1)$. I then look at $n!-n = n[(n-1)!-1]$ again if a prime $p$ divides $n$ I'll find that $p$ doesn't divide $n+1$. So I'm looking at $((n-1)!-1,n+1)$. I've looked at the first few n's and it seems that the gcd is either 1 or n+1. But I'm stuck on how to get there from $((n-1)!-1,n+1)$.   Can anybody provide a hint as to how to proceed?
71783
Prove that $n(n^2 - 1)(n + 2)$ is divisible by $4$ for any integer $n$   I can not understand how to prove it. Please help me.
24138
I was doing some basic Number Theory problems and came across this problem :     Show that if $a$ and $n$ are positive integers with $n\gt 1$ and $a^{n} - 1$ is prime, then $a = 2$ and $n$ is prime   My Solution : (Sloppy)        $a^{n}-1$ = $(a-1)$ . $(a^{n-1} + a^{n-2} + ... + a + 1)$   This means that $(a-1)$ | $(a^{n}-1)$    But $(a^{n}-1)$ is prime   So , $(a-1)$ = 1 $\Rightarrow$ $a = 2$   Now , let $n$ be composite   $n = kl$ , where $1 \lt k \lt n$ and $1 \lt l \lt n$   Now , $a^{kl}-1$ = $(a^{k}-1)$ . $(a^{k.{(l-1)}} + a^{k.{(l-2)}} + ... + a^k + 1)$   This means that $2^{n} -1$ is composite    Hence , we have achieved a contradiction      My Question : Am I correct ?
105585
$n &gt; 2$ and $n$ is a prime number then $n$ is odd.  Prove by contradiction assume $n$ is even then there is some $k\in\Bbb N, n = 2k$ then $n &gt;2, 2k &gt; 2 , k &gt; 1$  Is this  a sufficient proof?
36084
Let $a,b,c,d$ be natural numbers with $ab=cd$. Prove that $a+b+c+d$ is composite. I have my own solution for this (As posted) and i want to see if there is any other good proofs.
82769
I get some troubles with this problem, could you help me? Given prime numbers $p$ and $q$ prove $\exists k\in\mathbb{Z}$ such that $pn^q+qn^p+kn$ is a multiple of $pq,~\forall n\in\mathbb{Z}$.
107659
Prove or disprove $$\dfrac{n^2 + 1}{4k + 3} \notin \mathbb{Z}, n, k \in \mathbb{N}^{+}$$  I know if $n^2 + 1$ is prime if and only if $n^2 + 1 \equiv 1 \pmod 4$.
95975
For all primes $p\neq 2$, it's easy to see that $$p\equiv 1~\text{or}~3\pmod 4$$ I was wondering if it's equally likely ($50\%-50\%$) that prime modulo $4$ is $1$ or $3$. And if so, is there a simple proof?