Tag Info

Hot answers tagged coprime

20

Suppose that the gcd is not $1$. Then there is a prime $p$ that divides $ab$ and $a+b$. But then $p$ divides one of $a$ or $b$, say $a$. Since $p$ divides $a+b$, it follows that $p$ divides $b$. This contradicts the fact that $a$ and $b$ are relatively prime.

16

Yes, if $d$ and $q$ had a common factor, it would also be a factor of $d+q=p$. This is the heart of the Euclidean algorithm for greatest common divisor.

11

Your first examples are $L$-series of quadratic Dirichlet characters. If $\chi$ is a primitive Dirichlet character of conductor $N$ taking values in $\{\pm1\}$ and with $\chi(-1)=-1$ then $$\zeta(s)L(s,\chi)=\zeta_K(s)$$ where $K=\Bbb Q(\sqrt{-N})$ and $\zeta_K$ is the Dedekind zeta function of $K$. The analytic class number gives $$L(1,\chi)=\frac{2\pi h}{w\... 9 I was going to write more or less the same answer of Lord Shark, so let us steer in a more elementary direction. The fact that Gregory series equals \frac{\pi}{4} can be seen as a consequence of$$ \sum_{n\geq 0}\frac{(-1)^n}{2n+1}=\int_{0}^{1}\sum_{n\geq 0}(-1)^n x^{2n}\,dx = \int_{0}^{1}\frac{dx}{1+x^2}=\arctan(1)=\frac{\pi}{4}\tag{A}$$but since$$ \...

8

Your jump from "$k\mid a+b$ with $k\mid a$" to $ka=a+b$ seems to be wrong. Just because $k$ is a factor of $a$ doesn't mean at all that the number of times it divides $a+b$ is exactly $a$. That seems to kill the rest of your argument. Instead, here is an approach that doesn't mention prime factors at all. It starts from the well-known property that $(a,b)=1$...

8

Let $f(C)$ be the number of integers from $1$ to $C$ that are relatively prime to $N$. If we can compute $f(C)$, the rest is easy. Say we are allowing $A \le x\le B$. Then our answer is $f(B)-f(A-1)$. Note that $f(C)$ is $C$ minus the number of integers in the interval $[1,C]$ that are not relatively prime to $N$. Call this number $g(C)$. So $f(C)=C-g(C)$. ...

6

HINT: Suppose that $p$ is a prime that divides $ab$ and $a^2+b^2$. Then $p$ divides both $a^2+2ab+b^2=(a+b)^2$ and $a^2-2ab+b^2=(a-b)^2$. This in turn implies that $p$ divides both $a+b$ and $a-b$. (Why?) Use this to show that $p$ divides both $a$ and $b$.

6

Hint: $$x\in\langle a\rangle \cap\langle b\rangle\implies ord(x)\mid ord(a)\,,\,ord(b)\;\ldots$$

6

$$2^{364} - 1 = 3 \cdot 5 \cdot 29 \cdot 43 \cdot 53 \cdot 113 \cdot 127 \cdot 157 \cdot 911 \cdot 1093^2 \cdot 1613 \cdot 2731 \cdot 4733 \cdot 8191 \cdot \mbox{BIG}$$ and $$364 = 4 \cdot 7 \cdot 13$$   $$2^{1755} - 1 = 7 \cdot 31 \cdot 73 \cdot 79 \cdot 151 \cdot 271 \cdot 631 \cdot 937 \cdot 3511^2 \cdot 6553 \cdot 8191 \cdot \mbox{... 6 Yes, the Euclidean algorithm is a good starting point. In particular recall these properties of the \gcd. Hint. Since 3n-4 is not divisible by 3, we may consider$$\begin{align}\gcd(3n-4, n^2+1)&=\gcd(3n-4, 3n^2+3)\\&=\gcd(3n-4, (3n-4)(n+1)+n+7)\\&=\gcd(3n-4,n+7)\end{align}$$Can you take it from here? P.S. At end you will see that your ... 6 Let$$a_n=5^n+6^n$$Since 5,6 are the roots of$$0=(x-5)(x-6)=x^2-11x+30$$we deduce that the a_n satisfy the recursion$$a_n=11a_{n-1}-30a_{n-2}\quad a_0=2\quad a_1=11$$From this it is clear that if any a_n,a_{n-1} have a common factor for any n, that factor also divides a_{n-2}. (Note: we have \gcd(a_n,30)=1 for all n so we can disregard ... 5 If A and B are comparable in value, the algorithm for generating Farey sequence might suit you well; it generates all pairs of coprime integers (a,b) with 1\leq a<b\leq N with constant memory requirements and O(1) operations per output pair. Running it with N=\max(A,B) and filtering out pairs whose other component exceeds the other bound ... 5 Here's a partial answer (an answer to (1) and more of a comment about (2) and (3)). A lot of this can be found in this OEIS entry. 1) Not necessarily. If k=509203 (a Riesel Number), all of the terms are composite. 2) This is a hard problem, and I would be very surprised if anything of this form could be proven (problems of this form tend to be hard: as ... 5 No - any two coprime odd numbers (e.g any two primes \ne 2) provide a counterexample. 5 We begin by noting that the hypothesis x^3 y^3 = y^3 x^3 can actually be strengthened to$$(x^3 y^3)^n = (x^3)^n (y^3)^n \text{ for all } x,y \in G \text{ and } n \in \mathbb{N}. \tag{$\star$} $$The stronger version can be proved by induction. Perhaps it is worth commenting on the inductive step. If we assume that (x^3 y^3)^{n-1} = (x^3)^{n-1} (y^3)^{... 5 In this question it is shown that the probability two integers are coprime is \frac 6{\pi^2} in the sense that you choose the integers between 1 and N uniformly, then take the limit as N \to \infty. For the \gcd to be 2, you need both integers to be even, then the numbers that are half of each of them to be coprime. The chance is then \frac 14 ... 5 Note that if \gcd(a,b)=1, then \gcd(a+b,b)=1 There are 48 numbers which are less than 105 which are relatively prime to 105, since \phi(105)=48. Let a_i be the i-th number which is relatively prime to 105. It is clear that a_{48}=104. Also the first 104 numbers which are relatively prime are \{1,2,4,8,\ldots,104\}. The next 48 ... 4 \begin{eqnarray}\rm{\bf Hint}\,\ \ 1\!=\!(a,b)\!\overset{Bexout}\Rightarrow\! 1=\color{sienna}{ia\!+\!jb}\, \Rightarrow &&\rm \color{#0a0}{ab}c\!+\!(\color{blue}{a\!+\!b})d\! =\! (\color{sienna}{ia\!+\!jb})^2\! = \color{#c00}1\\ \rm thus\quad n\,\mid &&\rm \color{#0a0}{ab}\ \, \&\, \ \color{blue}{a\!+\!b}\,\ \Rightarrow\,\ n\mid\color{#... 4 HINT: a^2 + b^2 +2ab = (a+b)^2. 4 Let n have the property and let p be the smallest prime not dividing n. Then n<p^2 as otherwise \gcd(p^2,n)=1 destroys the property. On the other hand, this implies that n is a multiple of the product of all primes <p. For p\ge13, by Bertrand's postulate, the prime preceding p is >\frac p2 and the one preceding that is >\... 4 Consider the subgroup \langle b,c \rangle of F. As a subgroup of a free group, it is itself free, but a is in its centre, and the only free group with nontrivial centre is the infinite cyclic group. So \langle b,c \rangle = \langle g \rangle for some g \in F, and a = g^k for some k \in {\mathbb Z}. Since a is both a p-th power and a q-th ... 4 With N = 3, the definition of three integers being coprime is that the highest common factor of the three integers is 1. In other words, for any prime p, at least one of my three integers is not divisible by p. Thus, as N increases, it becomes easier for coprimality to be satisfied. I think you are thinking about the integers being pairwise ... 4 Such pair is called co-prime and a special case of an additive base \mathcal{B} of the natural numbers. Every subset of the natural numbers is called an additive base \mathcal{B} if there is a natural number h such that every sufficiently large natural number n can be constructed as sum of at most h numbers from \mathcal{B}. The largest number ... 4 Of course it is. If q and d have a common factor f: q = Qf d = Df then p = q + d = (Q +D)f and more generally kq\pm md = (kQ \pm mD)f will have that factor, too. 4 worth emphasizing that multiplying a (column) vector of integers by an integer (square) matrix with integer inverse (so determinant is \pm 1) preserves the gcd of the vector... Your (row) vector (a,b) is mapped to (a+2b, a+b); as columns, the matrix is$$ \left( \begin{array}{cc} 1 & 2 \\ 1 & 1 \end{array} \right) $$with determinant -1 If ... 4 Here is an alternative approach. You have$$a_n-b_n\sqrt{2}=(1-\sqrt{2})^n\,.$$That is,$$\begin{align}a_n^2-2b_n^2&=\big(a_n-b_n\sqrt2\big)(a_n+b_n\sqrt2\big)\\&=\big((1-\sqrt2)(1+\sqrt2)\big)^n=(-1)^n\,.\end{align}$$Thus,$$x_n\,a_n+y_n\,b_n=1\,,$$where x_n:=(-1)^n\,a_n and y_n:=-2\,(-1)^n\,b_n are integers. Thus, \gcd(a_n,b_n)=1. 4 6+10-15=1 and that's it but answer needs 30 characters. 4 As the comment stated, you want to use the Euler's totient function. A good way to calculate the totient function is the use of the product formula. We first note that the prime factorisation of 1260 = 2^2 \cdot 3^2 \cdot 5 \cdot 7. We then calculate$$\phi(1260) = 1260 \cdot (1 - \frac{1}{2})(1 - \frac{1}{3})(1 - \frac{1}{5})(1 - \frac{1}{7}) = 288$$. 4 Nice problem. Here it is. Let a_k=a^k+a^{k-1}-1. We will construct such a set inductively. First, take any k_1, and add a_{k_1} to the list. Now, let k_2=\phi(a_{k_1}), where \phi(\cdot) is the Euler's totient function. Since (a,a_k)=1 for every k, it follows from Euler's theorem that, a^{k_2+1}+a^{k_2}-1\equiv a\pmod{a_{k_1}}, which is ... 4 Claim:$$\boxed {5\prod_{i=0}^nk_i = k_{n+1}-2}$$Pf: Consider the product$$P_n=\prod_{i=0}^nk_i$$Since 5=6^{(2^0)}-1 we note that$$5P_n=\left(6^{(2^0)}-1\right)\times \left(6^{(2^0)}+1\right)\times \prod_{i=1}^nk_i =\left(6^{(2^1)}-1\right)\times \left(6^{(2^1)}+1\right)\times \prod_{i=2}^nk_i==\left(6^{(2^2)}-1\right)\times \left(6^{(2^2)}+1\...

Only top voted, non community-wiki answers of a minimum length are eligible