For a positive integer $n$, let $p(n)$ the largest prime divisor of $n$. Show that there exist infinitely many positive integers m such that $p(m − 1) &lt; p(m) &lt; p(m + 1)$.  Let $q$ be odd prime and $a&lt;b$. $q^{2^b} - 1 =(q-1)(q+1)(q^2+1)...(q^{2^{b-1}}+1)$ $q^{2^{a}}+1 $ is a divisor of $ q^{2^{b}}-1  $    I don't know how to get the required inequality.
122461
Let $p(n)$ denote the largest prime factor of $n$. Prove that there are infinitely many $n$ such that $$p(n)&lt;p(n+1)&lt;p(n+2).$$  Edit:   My solution: Choose $n=\prod_{i=1}^{k}p_i$, product of the first $k$ primes. This means that $n+1=\prod_{i=1}^{k}p_i+1$ is either a larger prime or has a prime factor larger than that of all factors of $n$. Still not sure about $n+2$.
118815
I have been given the following question in my homework:      Show that for every $n \in \mathbb{N}$ there are at least ${\log_2log_2 (n-1)}$ primes in $[1,n]$   I think it is related to euclidean and induction but I am having difficulties developing my solution.   Thanks for your help (:
30745
Let $p$ be a prime. Show that for all integers $x$, $x^2\equiv 1 (\text{mod} \ p) $ if and only if $x \equiv 1 (\text{mod} \ p)$ or $ x \equiv p-1 \ (\text{mod} \ p ). $    I know that I have to prove this both forward and backward. I'm not really sure where to begin
18783
Let $ a,b,c$ positive integer such that $ a + b + c \mid a^2 + b^2 + c^2$.   Show that $ a + b + c \mid a^n + b^n + c^n$ for infinitely many positive integer $ n$.   (problem composed by Laurentiu Panaitopol)  So far no idea.
104287
Show there are infinitely many primes that are equivalent to $1 \pmod{8}$.  Hello there! I have been trying to do this problem for a pretty long time with no avail.    I noticed that this is really similar to Euclid's proof that there are infinitely many primes.  However, I can't find a way to use that here.  Can anyone help me?
10928
Given an integer $n$, we are asked to investigate about the existence of integer divisors of $n^2+1$ of the form $4k+3$. Can you provide some insights about it?
4839
We can prove that there is no integer $n&gt;1$ such that $2^n-1\mid 3^n-1$. This leads to the following question:     Is it true that for every pair of primes $p&lt;q$ there are only finitely many integers $n$ such that $p^n-1\mid q^n-1$? Are there two primes $p&lt;q$ and an integer $n&gt;p+q$ such that $p^n-1\mid q^n-1$?Is it true that if $n&gt;6$ then $2^n-1\nmid 5^n-1$?   Edit: Here are some examples: \begin{array}{ll} 2^{36}-1\mid 41^{36}-1, &amp;3^{12}-1\mid 97^{12}-1,\\ 5^{6}-1\mid 37^{6}-1, &amp;7^{4}-1\mid 151^{4}-1. \end{array}  Now I prove there is no integer $n&gt;1$ such that $2^n-1\mid 3^n-1.$  Proof: Denote $A=2^n-1$ and $B=3^n-1$. If $n$ is even then $3$ divides $A$ but not $B$, a contradiction.  If $n$ is odd then $A\equiv -5\pmod {12}$. Since every prime greater than $3$ is $\equiv \pm1,\pm5 \pmod {12}$, some prime factor $p$ of $A$ must be congruent to $\pm5 \pmod {12}$. As $p \mid B$, we have $3^{n+1}\equiv 3 \pmod p$. Since $n+1$ is even, we get $(\frac{3}{p})=1$, a contradiction again.
86566
Fix $k \in \mathbb{Z}_+$. Prove that we can find infinitely many primes of the form $a2^k +1,$ where $a$ is a positive integer. We can use the result that: If $p \ne 2$ is a prime, and if $p$ divides $s^{2^t}+1$, for $s &gt; 1$ and $t \ge 1$, then $p \equiv 1 \pmod {2^{t+1}}$.  Ive trying to get something inductively: For $k = 1$, there are infinitely many primes of the form $2a + 1$. Suppose there are infinitely many primes of the form $a2^k + 1$, and then show that there are infinitely many primes of the form $a2^{k+1} + 1$. If there are infinitely primes of the form $a2^k + 1$, where $a$ is even, then we have that, $a2^k + 1 = (2q)2^k + 1 = q2^{k+1} + 1$. Hence we are done. Therefore, suppose there are only infinitely many primes of form $a2^k + 1$, where $a$ is odd. - but I can't get a contradiction out of this.
38927
How can I show that $(n-1)!\equiv-1 \pmod{n}$ if and only if $n$ is prime? Thanks.
109068
Find all positive integers $n$ such that $n$ is divisible by all the positive integers less than or equal to $\sqrt{n}$  My thought: If n is a positive integer, let d(n) denote the number of positive divisors of n and I will find n such that $d(n) \ge 2\sqrt{n} - 1$
45015
Let $f \in \mathbb{Z}[x]$ be non constant. How to prove that exists infinitely many primes such $f$ have root in $\mathbb{Z/_{(p)}}$. I spent much time, but with no benefits.
40575
Show that if $a$ and $b$ are positive integers with $(a,b)=1$ then $(a^n, b^n) = 1$ for all positive integers n  Hi everyone, for the proof to the above question,  Can I assume that since $(a, b) = 1$, then in the prime-power factorization of a and b, they have no prime factor in common, when they are taken to the $nth$ power, they will still have no prime factors in common, and so $(a^n, b^n) = 1$ for all positive integers n.  I think I'm jumping to conclusions here again, if so, leave some tips on how to do the proof properly, thanks :)  And also, I do not know how to approach the reverse problem where if $(a^n, b^n) = 1 then (a, b) = 1$, any guidance will be much appreciated!
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$.
46688
Here is an argument in my book.  Theorem If $n$ is a positive integer and $p$ is a prime, then the exponent of the highest power of p that divides $n!$ is $\sum_{k=1}^\infty [\frac{n}{p^k}]$ Proof&gt; Among the first $n$ positive integers, those divisible by $p$ are $p,2p,...,[n/p]p$. Thus, (Q1) there are exactly $[n/p]$ multiples of $p$ occurring in the product that defines $n!$, namely, $p,2p,...,[n/p]p$. The exponent of $p$ in the prime factorization of $n!$ is obtained by adding to the number of integers in $\{p,2p,...,[n/p]p\}$, the number of integers among $1,2,\cdots,n$ divisible by $p^2$, and so on. Reasoning as in the first paragraph, the integers between 1 and n that are divisible by $p^2$ are $p^2,\cdots,[n/{p^2}]p^2$. After a finite number of repetitions of this process, we are led to conclude that the total number of times $p$ divides $n!$ is $\sum_{k=1}^\infty [\frac{n}{p^k}]$  I completely don't get this argument from $(Q1)$. Why there are exactly $[n/p]$ multiples of $p$ in the prime factorization of $n!$?? Moreover, I don't get what the author is doing after $(Q1)$. Could someone please explain this argument in detail? Or please suggest me a link to see a proof for this theorem. I have googled it, but I couldn't find a proof for it. EDIT: I hate explaining things verbally. Please give me a formal argument..
4812
Problem: $(\forall a\in\mathbb{Z^+})(m\in\mathbb{Z^+}\to a^m\equiv a^{m-\phi(m)}\pmod{m})$  My work: Start by letting $m=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$. If $(a,p_i)=1$ for some integer $i$, then we have that  $$ a^{\phi(p_i^{a_i})}\equiv 1\pmod{p_i^{a_i}} $$ by Euler's theorem. Since $\phi(p_i^{a_i}) \mid \phi(m)$, we have that $p_i^{a_i}\mid (a^{\phi(m)}-1)$ if $(a,p_i)=1$.   Beyond this, I am stuck at the moment.
114720
I got stuck on this inequality for a day. If $p$ is positive integer, then the problem becomes too easy, but I can't find how we deal with the general case when p can be any positive number. Can someone give me a hint? I really appreciate     Prove that $|x^p - y^p| \le p|x-y|(x^{p-1} + y^{p-1})$ provided that $1 \le p \lt \infty$ and $x, y \ge 0$
107652
Find a prime number $p$ and an integer $b&lt;p$ such that $p$ divides $b^{p−1}−1$.  First I think of long divisions but it didn't work out. Now I'm stuck..