# Tagged Questions

This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.

62 views

### How do I demonstrate that a polynomial of degree $2$ divides one of degree $n$?

Let $f$ and $g$ the polynomials $$f(x) = (x+1)^{2n-1}+(-1)^n(x+2)^{n+1}\qquad\text{and}\qquad g(x) = x^2 + 3x + 3$$ How do I demonstrate that $g$ divides $f$? I tried finding the roots of $g$ then ...
40 views

### Given an integer $n$ and relatively prime positive integer $a$ and $b$, show that exactly one of $n$ and $ab-a-b-n$ is expressible in the form $ax+by$

Given an integer $n$ and relatively prime positive integers $a$ and $b$, show that exactly one of $n$ and $ab-a-b-n$ is expressible in the form $ax+by$ for some non-negative integers $x$ and $y$. ...
139 views

### Help with understanding this proof in discrete mathematics?

This is the question and solution: Q: Prove that for any integer $a$, $2a + 1$ and $4a^2$ + 1 are relatively prime. A: Since $4a^2 + 1 = (2a β 1)(2a + 1) + 2$, any common divisor of $2a + 1$ and ...
16k views

### For any prime $p > 3$, why is $p^2-1$ always divisible by 24?

I know this is very basic and old hat to many, but I love this question and I am interested in seeing whether there are any proofs beyond the two I already know.
60 views

747 views

### How can I find the possible values that $\gcd(a+b,a^2+b^2)$ can take, if $\gcd(a,b)=1$

If $\gcd(a,b)=1$, how can I find the values that $\gcd(a+b,a^2+b^2)$ can possibly take? I can't find a way to use any of the elemental divisibility and gcd theorems to find them.
514 views

### Suppose $(a,b)=1$, then $(2a+b,a+2b)=1\text{ or }3$.

Suppose $(a,b)=1$. Let $d=(2a+b,a+2b)$. Then $d=(2a+b)u+(a+2b)v=a(2u+v)+b(2v+u)$ where $u,v \in \mathbb{Z}$. Since $(a,b)=1$, then $a(2u+v)+b(2v+u)=1$. I'm not sure if I'm going in the right ...
43 views

### Let $k = (a+b,a^2+b^2-ab)$. If $(a,b)=1$ then $k = 1$ or $k=3$.

Yes, I know that this questions has two answers, but I can't see why $k$ can't be 27, or any other $3^n$ with $n \neq 2$.
### $\gcd( x+y, x^2 - xy + y^2)$ is 1 or 3 for coprime $x$, $y$ [duplicate]
How does one show that: if $\gcd( x, y) = 1$, then $\gcd( x+y, x^2 - xy + y^2) = 1\,{\rm or }\,3$.
### If $\gcd(a,b)=1$, then $\gcd(a+b,a^2 -ab+b^2)=1$ or $3$.
Hint: $a^2 -ab +b^2 = (a+b)^2 -3ab.$ I know we can say that there exists an $x,y$ such that $ax + by = 1$. So in this case, $(a+b)x + ((a+b)^2 -3ab)y =1.$ I thought setting $x = (a+b)$ and \$y = ...