How can  I determine all prime factor of  $\frac{3^{41} -1}{2}$ without doing prime factorizations.  Any help will be appreciated.
120506
Not sure how to go about this. Law of quadratic reciprocity and Euler's Criterion is recently learned material but I'm not sure how this applies.
123401
Prove that $2730$ divides $n^{13} - n$ for all integers $n$.   What I attempted is breaking $2730$ into $2, 3, 5$, and $7, 13$. Thus if I prove each prime factor divides by $n^{13} - n$ for all integers $n$, it will prove the original problem.   I already proved $2, 3$, and $5$ work. Struggling with how to do $91$?  Other solutions are welcome, but they should be associated with mod and solutions of this kind, because my answer should pertain to what was learned in class.  (Edit: Fixed the 91 problem, being slow today...In any case, I've got this problem now, so no answers are necessary. Posting my own soon.)
52795
Let $n$ be an integer, prove that every prime factor of $12x^2+1$ has the form $6m+1$, where $m$ is an integer.  I've gone as far as knowing that all primes $p&gt;3$ are either $6m+1$ or $6m-1$, how do I use this, not sure whether to even use that.  I know about the Legendre symbol and quadratic reciprocity
27033
Let $p$ be prime number ($p\gt2$) and $a,b\in\mathbb Z$ ,$a+b\neq0$ ,$\gcd(a,b)=1$ how to  prove that $$\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1~~\text{or}~~ p$$  Thanks in advance .
8423
If $n\in\mathbb N$ and $4^n+2^n+1$ is prime, prove that there exists an $m\in\mathbb N\cup\{0\}$ such that $n=3^m$.  I.e. if $4^n+2^n+1$ is prime, prove that $n=3^m$, where $m\in\mathbb N\cup\{0\}$.  I don't know how I could solve this, I don't have any ideas. I know that $4^n+2^n+1$ is obviously odd. Assume $m=0$, i.e. $n=1$. Then $3$ is prime. So that doesn't disprove what we're trying to show.  So assume $m&gt;0$. Then $4^n+2^n+1&gt;3$, so $4^n+2^n+1$ is either $3k+1$ or $3k+2$, where $k\in\mathbb N$. So either $4^n+2^n$ or $4^n+2^n-1$ is divisible by 3. I think it's not something that could help out at solving this. Just a little observation. I don't have any ideas.
92943
Let $p$ be a prime number such that $p \equiv 1 \pmod 4$. Prove that  $\frac{p^p-1}{p-1}$ is not prime.   We can rewrite $\frac{p^p-1}{p-1}$ as $$\dfrac{p^p-1}{p-1} = 1+p+p^2+\cdots+p^{p-1},$$but how do we show this is not prime?
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.
84624
For which primes $p$ is $2^p+1$ divisible by $p$?  What I have been doing is:  $2^p+1\equiv 0\pmod p$  $2^p\equiv -1\pmod p$  Then by Fermat's Theorem, we get  $2^p\equiv 2\pmod p$  This shows $p=1,3$.  I feel like this is not right though...
64054
I'm trying to prove that $a^n+1$ can only be prime if $n$ is a power of $2$. Is there a general factorization of $a^n+1$?
83266
For any positive integer $n$, let $\mathrm{PF}(n)$ denote the set of all distinct prime factors of $n$ (not counted with multiplicity).  The question (using the above notation) is: Is it true that for any two positive integers $m$ and $n$, $\phi(mn)=m\phi(n)$ if and only if $\mathrm{PF}(m) \subseteq \mathrm{PF}(n)$, where $\phi$ is the totient function?  Hint for the if direction: Any prime factor of $mn$ must either be a prime factor of $m$ or a prime factor of $n$ (by Euclid's lemma). But since any prime dividing $m$ also divides $n$, $mn$ has the same distinct prime factors as $n$, and hence any integer coprime to one of them is also coprime to the other.  Note that it is possible for $\mathrm{PF}(m) \subseteq \mathrm{PF}(n)$ to be true while $m \not\mid n$. For example, $4 \not\mid 2$, but they both have $2$ as the only prime factor. In this case, $\phi(8)=4=4 \cdot 1=4\phi(2)$.
32987
Prove that:  If $n$ is greater than 2, then $(3n)!$ is divisible by $n! \times  (n + 1)! \times  (n + 2)!$  From Barnard &amp; Child's "Higher Algebra".  I know that the highest power of a prime $p$ contained in $N$! is  $$ \left\lfloor{\frac{N}{p}}\right\rfloor + \left\lfloor{\frac{N}{p^2}}\right\rfloor + \left\lfloor{\frac{N}{p^3}}\right\rfloor ... $$  I'm unable to show that the formula above gives a higher value for $N = 3n$ than for the sum of its values when $N$ = $n$ , $n + 1$ and $n + 2$, considering the condition that $n &gt; 2$.
75836
I am reading a math book. It states the following rule:      For an integer $n$ greater than 1, let the prime factorization of $n$ be $$n=p^a_1p^b_2p^c_3...p^m_k$$    Here $a, b, c,..., m$ are nonnegative integers, and $p_1,p_1,...,p_k$ are prime numbers. Then the number of divisors of $n$ is: $$d(n)=(a+1)(b+1)(c+1)...(m+1)$$   I can use the rule to solve problems correctly, but I don't understand the rule. How to prove it?
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?
104546
My question is about number theory about the prime numbers.  Here is the question:  Prove that there is only one prime trio of the form $p$,$p+2$,$p+4$.  I mean,we can only find the primes 3,5,7  That satisfies the condition.
9407
If $a_1,a_2,\ldots, a_n$ are distinct primes, and $a_1=2$, and $n&gt;1$, then $a_1a_2\cdots a_n+1$ is of the form $4k+3$.  I have no ideas how to approach this question. Any hints?
84220
Calculate the remainder of the division of $1160^{602}$ by $35$. What I thought of doing right away is to factor out $602$ until I get to a point where I can apply Fermat's theorem. However, $35$ is not a prime number. How to proceed in this case?
62680
If $n = 51! +1$, Then find no of primes among $n+1,n+2,\ldots, n+50$  Really speaking, I don't have any clue ...