New answers tagged gcd-and-lcm
1
vote
Is it true that this quadruple sum involving $f(x,y,z,p)=x^p+y^p−z^p$, is equal to the sequence $1,0,0,0,...$ only if $p=1$ or $p=2$?
Outline/long comment:
\begin{align*}
s(n) &= \sum_{z=1}^n \sum_{y=1}^n \sum_{x=1}^n g \bigl( \gcd (f(x,y,z,p),n) \bigr) \\
&= \sum_{z=1}^n \sum_{y=1}^n \sum_{x=1}^n \sum_{d\mid \gcd (f(x,y,z,p)...
- 85.2k
2
votes
Find a number that will have $\gcd(n, m)^2 = \text {lcm}(n, m)$ with other 20 numbers at least
Suppose we had a "good" pair $(n,m)$. Write $n=\prod p_i^{n_i}$ and $m=\prod p_i^{m_i}$ for the two prime factorizations.
Then your condition is equivalent to $$2\min (n_i, m_i)=\max (n_i, ...
- 72.8k
-2
votes
Find a number that will have $\gcd(n, m)^2 = \text {lcm}(n, m)$ with other 20 numbers at least
The problem is equivalent to $nm=\gcd(n,m)^3$. Set
$n=\prod_i p_i^{a_i}$ and
$m=\prod_i p_i^{b_i}$. Hence
$$
\prod_i p_i^{a_i+b_i}=\prod_i p_i^{3\min\{a_i,b_i\}}
$$
so
$a_i+b_i=3\min\{a_i,b_i\}$. If $...
- 4,961
0
votes
How do I extend this integral solution to non-relatively prime $a$ and $b$?
My first answer was very wrong; I've hopefully made amends by changing it to a correct answer, but it's not a complete answer, merely a suggested approach.
The crucial term to evaluate in the first ...
- 85.2k
-1
votes
How many $n$ such that $\gcd(n,1)+\gcd(n,2)+\gcd(n,3)=\gcd(n,4)$
Sort of a long answer.
note that $gcd(1,n)=1 \ \forall \ n \in \mathbb{Z}/\{0\}$
Looking at n modulo 6,
n $\in \{6k,6k+1,6k+2,6k+3,6k+4,6k+5 \ | \ k\in \mathbb{Z}\}$
$ \forall n = 6k,\ k \in \mathbb{Z}...
0
votes
Accepted
How many $n$ such that $\gcd(n,1)+\gcd(n,2)+\gcd(n,3)=\gcd(n,4)$
Firstly, count of numbers divisible by $4$
$$\left\lfloor \frac{2023}{4} \right\rfloor = 505$$
Then, count of numbers divisible by both $4$ and $3$ (LCM of $4$ and $3$ is $12$):
$$
\left\lfloor \frac{...
- 149
4
votes
Accepted
What am I doing wrong in evaluating $\sum_{i=1}^{2024} \gcd(i,8)\;$?
I spotted two mistakes:
The number of $i\in\{1,\dots,2024\}$ that are relatively prime to $8$ is not $882$ but rather $1012$. Indeed, the integers relatively prime to $8$ are precisely the odd ...
- 85.2k
-1
votes
Accepted
When do we have $\gcd(a+b, sc)=1$, provided $\gcd(a,c)=1$, $\gcd(b,c)=1$?
As far as I understand, there are two ways to interpret the objective in this problem:
finding constant integers $r,s$ such that $\gcd(ra+b,sc) = 1$ for all pairwise coprime positive integers $a,b,c$,...
- 734
1
vote
show that $F[x]/q(x)= F[x]/p_1(x)\bigoplus \cdots \bigoplus F[x]/p_k(x)$
Let $q=p_1\cdots p_k$, and note that since $p_i$ is irreducible for all $i$, we have that $(p_i)+(p_j)=F[x]$. Indeed, this holds for any polynomial ring over a field see here for instance.
Since have ...
- 4,029
1
vote
Sum of residues $\sum_{s=1}^{n-1} r_s$
Claim: $$n \text{ prime} \iff S’ := \sum_{a=1}^{n-1} \sum_{b=1}^{n-1} ab \bmod n = \frac{n(n-1)^2}{2} $$
Proof: $\implies$
$$S’= \sum_{a=1}^{n-1} \sum_{b=1}^{n-1} ab \bmod n \overset{(1.1)}{=} \sum_{...
- 3,846
3
votes
Accepted
Sum of residues $\sum_{s=1}^{n-1} r_s$
For simpler algebra, let
$$d = \gcd(m, n), \;\; m = m^\prime d, \;\; n = n^\prime d, \;\; \gcd(m^\prime, n^\prime) = 1$$
We have for $0 \le s \le n - 1$ that
$$sm = \left\lfloor\frac{sm}{n}\right\...
- 50.5k
0
votes
The difference between the HCF and LCM of $x$ and $18$ is $120$. Find $x$.
Let $\alpha=gcd(x,18)$ & $\beta=lcm(x,18)$
Then
$\beta=\frac{18x}{\alpha}$ (as $18x=\alpha\beta$)
According to the problem the difference between $\beta$ and $\alpha$ is 120 i.e. $\beta-\alpha=120$...
0
votes
What exactly does the extended Euclidean algorithm compute for polynomials over a commutative ring?
I'm only aware of an extended Euclidean algorithm for elements of an Euclidean domain. $A[x]$ is an Euclidean domain iff $A$ is a field.
Regardless, even if there is a more general algorithm that ...
- 22k
Top 50 recent answers are included