Hot answers tagged

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