It is given to me that r, s and t are prime numbers and that p, q are two positive integers such that the LCM of p and q is $$N=r^2t^4s^2  $$ and we want to find the numer of ordered pairs (p, q).   Here since LCM of (p, q)  is N then both the numbers must be divisors of N.  If we calculate the total number of divisors of N we get 45 divisors which means that our (p, q) belongs to a set of these 45 divisors. Hence number of ways of choosing the two numbers are C(45,2) and then we arrange them in 2! ways thus getting  $$ \binom{45 } { 2 }  \cdot 2!$$ But my answer deviates completely from the actualy answet which truly implies that maybe my whole method is wrong.  Can anybody help me in this problem?
121865
If $r,s,t$ are prime numbers and $p,q$ are the positive integers such that LCM of $p,q$ is $r^2s^4t^2$, then the number of ordered pairs $(p,q)$ is?  My attempt to the solution:  Let $r^a s^b t^c$ be the LCM where $a=2,b=4,c=2$  Then the cases that arise are  I case   1) $p$ has $r^as^bt^c$ then there are a total of $(2+1)(4+1)(2+1)$ options  II case   1) $p$ has $r^as^b$ or $s^bt^c$,$r^at^c$ then there are total of $(2+1)(4+1)(2+1)(3)$ options.  The answers comes out to be $45*4$ but the answer is $45*5$. Which case am I missing?
87152
I am trying to find the smallest positive integer $n$ such that $S_n$ contains an element of order 60. I know that every permutation in $S_n$ can be expressed as the product of disjoint cycles, and I also know that the order of a permutation is the least common multiple of the lengths of the cycles in its disjoint cycle product.   So, suppose $\sigma \in S_n$ such that $|\sigma|=60$. Then $60=lcm \left\{|c_1|, \ldots , |c_m|  \right\}$, where $c_i$ is one of the cycles in the disjoint cycle product of $\sigma$. The prime factorization of 60 is $2^2\cdot 3 \cdot 5$, but the least common multiple of 2, 3, and 5 is 30, so that doesn't help. However, the least common multiple of 3, 4, and 5 is 60. I just don't know where to go from here.  Also, what is meant by a "disjoint cycle pattern"? Thanks for your help!!
107122
Given $p$ is prime number, find all pairs of positive integers $m,n$ such that $\gcd(m,n)=1$ and  $$\frac{p+m}{p+n}-\frac{m}{n}=\frac{1}{p^{2}}$$  We can write this equation as: $$\frac{p(n-m)}{n(p+n)} = \frac{1}{p^2}$$    Since we have positive RHS and $n(p+n)&gt;0$, we also have: $$p(n-m)&gt;0 \implies n&gt;m$$ I found that $n&gt;m$, but I have no idea to complete. Please give me some ideas, thank you very much!!
45388
If I know the GCD of 20 numbers, and know the 20 numbers, is there a formula such that I input the 20 numbers and input their GCD, and it outputs their LCM? I know that $$\frac{\left| a\cdot b\right|}{\gcd(a,b)} = \text{lcm}(a,b).$$ So is it$$\frac{\left| a\cdot b\cdot c\cdot d\cdot e\cdot f\right|}{\gcd(a,b,c,d,e,f)}?$$If not, what is it?
124083
Let $a$ and $b$ be two integers. Prove that  $$ dm = \left|ab\right| ,$$ where $d = \gcd\left(a,b\right)$ and $m = \operatorname{lcm}\left(a,b\right)$.   So I went about by saying that $a = p_1p_2...p_n$ where each $p_n$ is a prime. Same applies to $b = q_1q_2 ... q_c$. So then $m = (u_1u_2...)(p_1p_2...p_n)$ and $m = (t_1t_2...)(q_1q_2...q_c)$ since $a|m$ and $b|m$. $m$ has a unique factorization, so the primes $(u_1u_2...)(p_1p_2...p_n) = (t_1t_2...)(q_1q_2...q_n)$ and the gcd(a,b) = $(p_1p_2...p_n) \cap (q_1q_2...q_n)$ (I know this is not mathematically correct, so is there a correct way to express this?).   So $dm = |ab| \iff d= \frac{|ab|}{m}$. And by the definition above, $\frac{ab}{(t_1t_2...)b} = \frac{a}{(t_1t_2...)}$. And this is where I get stuck. Is my proof right? Am I going in the right direction?  Thanks   PS. I am trying to do this using only the prime factorization theorem and the definitions of the gcd and the lcm.
14942
This is the proof from the book:     Theorem. There are infinitely many primes of the form $4n+3$.    Lemma. If $a$ and $b$ are integers, both of the form $4n + 1$, then the product $ab$ is also in this form.  Proof of Theorem: Let assume that there are only a finite number of primes of the form $4n + 3$, say  $$p_0, p_1, p_2, \ldots, p_r.$$ Let $$Q = 4p_1p_2p_3\cdots p_r + 3.$$ Then there is at least one prime in the factorization of $Q$ of the form $4n + 3$. Otherwise, all of these primes would be of the form $4n + 1$, and by the Lemma above, this would imply that $Q$ would also be of this form, which is a contradiction. However, none of the prime $p_0, p_1,\ldots, p_n$ divides $Q$. The prime $3$ does not divide $Q$, for if $3|Q$  then $$3|(Q-3) = 4p_1p_2p_3\cdots p_r,$$ which is a contradiction. Likewise, none of the primes $p_j$ can divides $Q$, because $p_j | Q$ implies $p_j | ( Q - 4p_1p_2\cdots p_r ) = 3$, which is absurd. Hence, there are infinitely many primes of the form $4n +3$.   END  From "however, none of the prime ...." to the end, I totally lost!    My questions:   Is the author assuming $Q$ is prime or is not? Why none of the primes $p_0, p_1,\ldots, p_r$ divide $Q$? Based on what argument?     Can anyone share me a better proof?     Thanks.
33895
A method to finding the LCM of two numbers is to use prime factoring. I know how to do this, but logically why does this work in finding the lcm
100946
The  (ESC), states that for every natural number $n \geq 2$, there exists a set of natural numbers $a, b, c$ , such that the following equation is satisfied:  $$\frac{4}{n}=\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\tag{1}$$  The basic approach to solving this problem outlined by Mordell [Ref1] is described below  By defining $t$ and $m$ as positive integers greater than zero and $q$ a positive integer greater than one we can observe that  a) There is always a solution for even $n$, since if $n=2^qt$ we have the trivial solution $$\frac{4}{4t}=\frac{1}{t}$$  In the remaining case $n=2(2t+1)$, a solution in the form of two Egyptian fractions can always be found  e.g. $$\frac{4}{2(2t+1)}=\frac{2}{2t+1}=\frac{1}{t+1}+\frac{1}{(t+1)(2t+1)}$$  b) If $(1)$ is a solution for some particular prime $n$ then all composite numbers $mn$ divisible by $n$ are also solutions, thus  $$\frac{4}{mn}=\frac{1}{ma}+\frac{1}{mb}+\frac{1}{mc}$$  will also be a solution. This means that we can simplify the analysis to the cases where $n$ is a prime greater than 2.  Using Mordell's approach we have just shown that we only need to consider the cases where $n$ is prime and where $n \equiv 1 \pmod{2} \;\;[meaning \;\;n=2t+1]$  The argument continues...  Mordell goes on to show in turn that the search can be reduced further to the cases when $$n \equiv 1 \pmod{4} \;\;[meaning \;numbers \;\;n=4t+1]$$ $$n \equiv 1 \pmod{8} \;\;[meaning \;numbers \;\;n=8t+1]$$ $$n \equiv 1 \pmod{3} \;\;[meaning \;numbers \;\;n=3t+1]$$ $$n \equiv 1,2,4 \pmod{7} \;\;[meaning \;numbers \;\;n=7t+1,n=7t+2 \;or\;n=7t+4 ]$$ $$n \equiv 1,4 \pmod{5}  \;\;[meaning \;numbers \;\; n=5t+1 \;or\;n=5t+4]$$  Assembling these results together, Mordell showed that the conjecture can be proved in this context except for the cases when $$n \equiv 1,11^2,13^2,17^2,19^2,23^2 \pmod{840}$$  Mordell stated that since the first prime meeting this condition is 1009, this is proof that the conjecture holds for $n&lt;1009$.  This basic approach can be pursued further. Other workers have shown that the conjecture holds for much higher values of $n$ using similar methods as can be seen on the above Wikipedia page.   Note that other intermediate results can be constructed from the above congruence's, e.g. $n \equiv 1 \pmod{24}$.  The question is:  Are there any other elementary approaches to solving this problem than the one outlined by Mordell (and described above)?  [Ref1] Louis J. Mordell (1969) Diophantine Equations, Academic Press, London, pp. 287-290.
74035
Suppose that $n \in \mathbb{N}$ is composite and has a prime factor $q$. If $k \in \mathbb{Z}$ is the greatest number for which $q^k$ divides $n$, how can I show that $q^k$ does not divide ${{n}\choose{q}}$?  Clearly, since $$ {{n}\choose{q}} = \frac{n!}{(n-q)!q!} = \frac{n(n-1)(n-2) \dots (n-q+1)}{q!} $$ So it suffices to show that, no element of the set $$ \left\{ n-1, n-2, \dots, n-q+1 \right\} $$ is divisible by $q$, which is clearly true, but I am unsure of how to show this rigourously.
33216
I considered an even number $n\geq 10$, where it is divisible by some positive integer $k$.  Also, $k$ divides $\frac{n}{2}$. Then $n = kq\implies k\cdot\frac{q}{2} = \frac{n}{2}$.  Can we say that $q$ is even in this case? Can anyone help to get it theoretically? Thanks a lot for the help.   PS.   From the answer given by Bill, it does not satisfy if we take $n=18,k=3,j=9.$ Kindly help. Let me rectify where I am going wrong. Please help.  $\quad\ \ \ \ \ \ \ \ \ $ If $\,\rm\ J,K\mid N\,\ $  then $\rm\,\ \color{#c00}K\ {\LARGE \mid} {\Large  \frac{N}{\color{#0a0}J}}\! \iff\color{#0a0}J\ {\LARGE \mid} {\Large \frac{N}{\color{#c00}K}}\, $ [$\rm\!\!\iff\!\!  JK\mid N\,$]  This part is not satisfied.
53508
What made me have a question is the following problem.     The prime divisors $p\not=5$ of the integer $n^2+n-1$ are of the form   $10k+1$ or $10k+9$.   I thought $\left(\frac 5 p\right) = 1$, because $5 \equiv 1 \pmod 4$.  So $\left(\frac 5 p\right) = (-1)^{p-1}\left(\frac p 5\right)=1$ by qudratic reciprocity.  Then $p$ should be of the form $2k+1$  But I think there is something wrong, and I have lost.  Is there someone to help me?
19157
I'm trying to understand this proof from Stein's Elementary Number Theory, and I understand the pairing of inverses but not the other direction. I have two questions:  $1).$ When the proof says, $l$ a prime divisor of $p$, and so $l&lt;p$ and $l \mid (p-1)!$, is this because $l \mid p \Rightarrow l \mid p!=p*(p-1)!$ and so $l \mid (p-1)!$ (by Euclid)?  $2.)$ Why is it that $p \mid ((p-1)!+1)$?
11111
Let $Y(k)$ be the number consisting of $1$, repeated $k$ times. We know that $Y(2) =11$ is prime. It so happens that $Y(19)$ and $Y(23)$ are also prime.   Are there any more?   Regards,  David
36962
In Euclid's proof, if $p_1, p_2, \dots, p_n$ are the only primes then $p_1 \times p_2 \times \dots \times p_n + 1$ is not divisible by any of $p_1, p_2, \dots, p_n$ (because of some algebraic facts), which makes another prime and is a contradiction.   The proof makes sense logically, and I tried some numerical examples to "feel" the proof better but...  $2 \times 3 \times 5\times 7\times 11\times 13+1$ is not a prime! $2 \times 3 \times 5\times 7\times 11\times 13 \times 17+1$ is also not prime! Why is the general case proof is not working for these examples?
12560
If $p$ and $q$ are distinct primes such that $p|c$ and $q|c$, prove that $pq|c$ ..  I start with this:   if $c=pk$  and $c=qt$ then $q|pk$ and $p|qt$  but a couldn't get the solution.  I need your help
52019
After some trials, I found out that a prime $p \gt 5$ is congruent to $q\pmod{30}$, where $q$ is also a prime, and $1 \le q \lt 30 \;$ (i.e.  $p \equiv q\pmod{30}.$  Is there a way to write a formal proof to show this?  Is that an acceptable answer.
14728
Suppose there are $2$ permutations given by $p$ and $q$. I need to check whether $p$ belongs to the group generated by $q$, and if so, it's representation in a power of $q$. In other words, I've been given $p$ and $q$, I need to check whether $\exists i \in \{ 0,...,|q|-1 \} \text{ such that } p = q^i$ I know that if $m = \gcd(i, |q|)$, then $|q^i| = \frac{|q|}{m}$. Now, say that such an $i$ exists. Then, $$ |p| = \frac{|q|}{\gcd(i, |q|)} \Rightarrow \gcd(i, |q|) = \frac{|q|}{|p|} $$ Thus, a necessary condition for such an $i$ to exist is: $|p|$ divides $|q|$ Say that this holds, and $\frac{|q|}{|p|} = r$, where r is an integer. Then we just have to solve $\gcd(i, |q|) = r$ for $ i \in \{ 0,...,|q|-1 \}$. Can this be done? If not manually, then by some efficient algorithm? (Note: Just looping over all values of $i$ is not efficient as $i$ may be very large) Edit: Another way I can think of solving this is by writing both $p$ and $q$ as product of disjoint cycles: $$ p = c_1c_2\ldots c_k \text{ and } q = d_1d_2\ldots d_l $$ And thus, as disjoint cycles commute: $$ p^i = c_1^ic_2^i\ldots c_k^i $$ How to proceed after this?