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

learn more… | top users | synonyms (1)

2
votes
2answers
92 views

Extended Euclidean Algorithm problem

I'm confused about how to do the extended algorithm. For example, here's the gcd part gcd(8000,7001) $$\begin{align}8000 &= 7001\cdot1 + 999\\ 7001&=999\cdot 7+8\\ 999&=8\cdot 124+7\\ ...
2
votes
7answers
379 views

Prove that $n(n^2 - 1)(n + 2)$ is divisible by $4$ for any integer $n$

Prove that $n(n^2 - 1)(n + 2)$ is divisible by $4$ for any integer $n$ I can not understand how to prove it. Please help me.
1
vote
1answer
86 views

If $m,n\in \mathbb N$ and $n>m$, prove that $lcm(m,n)+lcm(m+1,n+1)>\frac{2mn}{\sqrt{n-m}}$.

Where $lcm$ is the least common multiple. I've changed it to: $$\frac{mn}{\gcd(m,n)}+\frac{(m+1)(n+1)}{\gcd(m+1,n+1)}>\frac{2mn}{\sqrt{n-m}}$$ Can't see how to continue. Is there a way to ...
1
vote
2answers
69 views

Whether m divides n! or not?

I have a big number ($n!$). And I want to know whether $n!$ dividable by $m$ or not. Well calculating $n!$ is not a good idea so I'm looking for another way. Example: $9$ divides $6!$ $27$ does ...
2
votes
2answers
90 views

Number of Solutions

How to to calculate the number of solutions for the equation $A+B-\gcd(A,B)=R$ where we are given $R$ in the question ? In this question we have to calculate the number of combinations of $A$ and $B$ ...
1
vote
2answers
44 views

Is this a valid proof that $\{ax + by|x,y \in \Bbb Z\}= \{n\times \gcd(a, b) |n\in \Bbb Z\}$?

I'm trying to prove that $\{ax + by|x,y \in \Bbb Z\}= \{n\times \gcd(a, b) |n\in \Bbb Z\}$, but I'm unsure on the . The main proposition I'm using to solve this is that $\exists x,y, ax+by = \gcd(a, ...
1
vote
1answer
50 views

Prove thant if $a/b + c/d \in \mathbb Z, (a:b)= 1, (c:d) =1 $ then $|b|=|d|$

Be $a,b,c,d \in \mathbb Z, b \ne 0, d \ne 0.$ Prove that if $a/b + c/d \in \mathbb Z, (a:b)= 1, (c:d) =1 $ then $|b|=|d|$
4
votes
1answer
85 views

Simple method for $\frac{(2n+1)!}{(n!)^{2}}$ divide $lcm(1,2,\ldots,2n+1)$

The question is to prove that $\frac{(2n+1)!}{(n!)^{2}}$ divides $lcm(1,2,\ldots,2n+1)$. This seems like it should be a simple question, but try as I might, I can't seems to find any way that does ...
0
votes
3answers
79 views

If $a|(b-c)$ does it follow that $a|(b+c)$?

I plug in numbers and this seems to work but how can this be proved? If: $a|(b-c)\space \rightarrow\space ak=b-c$, but I can't see how this would mean $a|(b+c)$ If this is true, how can this be ...
0
votes
2answers
37 views

Prove $(\forall n \in \Bbb N)[\gcd\left(n,(16n+1)^3\right)=1]$

Prove $(\forall n \in \Bbb N)[\gcd(n,(16n+1)^3)=1]$ Knowing that $\gcd(a,b)=\gcd(a,b+a\times k)$ with $k \in \Bbb Z$ $$\gcd\left(n,(16n+1)^3\right)=\gcd\left((16n+1)^3,n\right)=d$$ ...
1
vote
2answers
48 views

Proof about GCD's

Prove that if $a, b$ and $c$ are integers with $b \neq 0$ and $a=bx+cy$ for some integers $x$ and $y$, then $\text{gcd}(b,c) \le \text{gcd}(a,b).$ I don't understand how to show (b,c) is less than ...
0
votes
1answer
49 views

Inductive proof for gcd

Proof that $(\forall n \in \Bbb N)[\gcd(n,(25n+1)^3)=1]$ By the inductive method: $p(n):\gcd(n,(25n+1)^3)=1$ $p(1): \gcd(1,26^3)=1 \implies p(n)\equiv \text{True}$ $p(n): $I assume that $p(n)\equiv ...
3
votes
3answers
68 views

Show that there are infinitely many values of n for which $23| n^2 + 14n + 47$

Show that there are infinitely many values of n for which $23| n^2 + 14n + 47$ So far I have shown that there is in fact some solution. By the definition of division, $n^2 + 14n +47 = 23k$ Thus, ...
1
vote
2answers
116 views

Let $d$ be a positive odd integer. Prove that there exists a positive $n \le d$ such that $d | 2^n − 1$.

I'm stuck on this question from my textbook which doesn't even have a solution. Any ideas ?. Help would be much appreciated. $$ d\, \left\vert\right.\, \left(2^{n} − 1\right) $$
2
votes
5answers
116 views

How to prove that $x^a-1|x^b-1 \Longleftrightarrow a|b$.

Prove that $x^a-1|x^b-1 \Longleftrightarrow a|b$, where $x \ge 2$ and $a,b,x \in \Bbb Z$. I've tried the following in attempting to solve this: $$a|b \rightarrow aq=b \rightarrow x^{aq}=x^b ...
0
votes
2answers
48 views

What are a and b?

$a$ and $b$ are two positive integers. If $ab=1260$, $gcd(a,b)=3$, and when $a$ is divided by $b$ the remainder is 18, what are $a$ and $b$? How do you solve this? EDIT It looks like an ...
2
votes
4answers
80 views

Prove: If $\gcd(a,b) = 1$ and $c|a$ and $d|b$, then $\gcd(c,d)=1$

I've a problem proving the following: If $\gcd(a,b) = 1$ and $c|a$ and $d|b$, then $\gcd(c,d)=1$ I've tried to set $a = c\cdot p$ and $b = d\cdot q$. But then I'm stuck proofing it formally.
1
vote
1answer
64 views

Prime power factorization of $10^n+1$

I have bee trying to prove/disprove the statement, $$\text{Let}\; 10^n+1 = p_{k}^{\;\alpha_k}p_{k-1}^{\;\alpha_{k-1}}\dots p_0, \text{where each}\; p_i \;\text{is a distinct prime.} \text{Then}\; ...
2
votes
2answers
107 views

If $a,b,c \in \mathbb N$ and $\gcd(a^2-1,b^2-1,c^2-1)=1$, prove that $\gcd(ab+c,bc+a,ca+b)=\gcd(a,b,c)$.

The whole problem is in the title. I'm out of ideas and can't think of a way to solve this, so I'd like to get some help. Thanks.
4
votes
2answers
125 views

$2^5 \cdot a^b=2,5ab$

I came across this problem in an elementary number theory book, and I think I solved it. Well, the question is posed as $2^5 \cdot 9^2 = 2,592$. Are there any other pairs $a,b \in \mathbb{Z}$ such ...
8
votes
1answer
432 views

$f'/f\in\mathbb{Z}[[x]]$ for polynomials vs. formal power series $f$

I am curious about the following problem from MIT's Problem Solving Seminar (#26 here, though the link may stop working after a few weeks): Let $f(x) = a_0+a_1x+\cdots\in\mathbb{Z}[[x]]$ be a ...
1
vote
1answer
86 views

If $a,b \in\mathbb N$ and $\gcd(a,b)=1$, prove that $\gcd(a+b;a^2+b^2)= 1$ or $2$.

If $a,b \in\mathbb N$ and $\gcd(a,b)=1$, prove that $\gcd(a+b,a^2+b^2)$ is always equal to either 1 or 2, where $\gcd$ is the greatest common divisor. I haven't really ever solved a problem like this ...
1
vote
0answers
57 views

Is it possible to find the least common divisor of a two numbers that are not relatively prime in polynomial time?

As the question states: Is it possible to find the least common divisor of two number that are not relatively prime in polynomial time? If so, how? Thanks!
2
votes
2answers
78 views

Proof that $\gcd$ divides $\operatorname{lcm}$

Show that the following conditions are equivalent: i) There exist positive integers $a, b$ such that $\gcd(a,b)=d$ and $\operatorname{lcm}(a,b)=m$. ii) $d\mid m$
2
votes
2answers
74 views

What is the highest power of a prime that divides nPr?

I know that the highest power of a prime which divides $n!$ is given by $$\left[\frac np\right]+\left[\frac n{p^2}\right]+\left[\frac n{p^3}\right]...$$ Where $[x]$ is the greatest integer function. ...
1
vote
6answers
298 views

Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers.

Let $m$ and $n$ be two integers. Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers. I think I have to use the contrapositive to solve this. So I assume $\neg ...
0
votes
1answer
374 views

Every natural number greater than 1 is divisible by a prime number

Sorry if this question has been asked, but a couldn't find one using the method I need. I want to prove that every natural number greater than 1 is divisible by some prime number using the WOP. I ...
0
votes
2answers
41 views

Question about Divisibility

Suppose we are given the following: $p$ is a prime number; $a, c \in \mathbb{Z}$ and $ n \in \mathbb{N}$. Can I prove that there exists $m \in \mathbb{N} $ and $b \in \mathbb {Z} $ such that ...
-1
votes
2answers
54 views

For any integer $n\ge0$ it follows that $9\mathrel|(4^{3n}+8)$?

I have been trying to use induction in order to prove the above statement but I always reach a dead end. How can this statement proven via induction? Thank you!
0
votes
1answer
82 views

Proof polynomial is always divisible by number

Given $f(x) \in \mathbb{Z} [x] $ a polinomyal, that evaluated in any $a \in \mathbb{N} $, results allways in a multiple of 101 or a multiple of 107 (both prime numbers). Prove then, that $f(x)$ it's ...
0
votes
2answers
129 views

Polynomial divisibility

Given $p(x) \in \mathbb Q[x] $ an irreducible polynomial, and $\alpha \in\mathbb C $ root of $p(x)$. Prove that if $q(x) \in \mathbb Q[x]$ it's a polynomial, such $q(\alpha) = 0$ then $p(x) \mid ...
1
vote
5answers
73 views

Show that if $(a,b)=1$, $a\mid c$ and $b\mid c$, then $a\cdot b\mid c$

Show that if $(a,b)=1$, $a\mid c$ and $b\mid c$, then $a\cdot b\mid c$. Tried $c=a\cdot k$ and $c=b\cdot j$ with $k,j\in\mathbb{N}$ then $a\cdot b\mid c^2=c\cdot c$.
3
votes
2answers
68 views

Why is the coefficient in front of $\sqrt n$ always 1 in the intermediate terms for finding the continued fraction expansion of $\sqrt n$?

After playing around on paper for a bit, I came up with a short python generator to find the continued fraction expansion of $\sqrt n$. I understand why it gets the right answer when it gets an ...
2
votes
2answers
447 views

how many pairs $(A, B)$ are there such that: gcd $(A, B) = A \oplus B$

Given an integer N,how can I find how many pairs $(A, B)$ are there such that: gcd $(A, B) = $A$ \oplus B$ where $ 1 ≤ B ≤ A ≤ N $. Here gcd $(A, B)$ means the greatest common divisor of the ...
0
votes
1answer
45 views

gcd & lcm in a PID

In a PID, $l={\rm lcm}(a,b)$ and $d=\gcd(a,b)$. Is it always true that the following product ideals are equal? $$<d><l> = <a><b>$$ Thanks in advance -- Mike
0
votes
0answers
115 views

Dynamic programming algorithm for GCD?

I can't seem to find a clear answer on this. I'm inclined to believe that there is not a DP solution for GCD, given the lack of information so far in my searches on the subject. I suppose that in ...
0
votes
0answers
56 views

Distribution and upper bound of mimic numbers

Let the notation $ a\mid b $ denote ''$ a $ divides $ b $''. The mimic function in number theory is defined as follows [1]. Definition For any positive integer $ \mathcal{N} = ...
2
votes
3answers
117 views

How to prove or disprove that $\gcd(ab, c) = \gcd(a, b) \times \gcd(b, c)$?

I'm new to proofs, and am trying to solve this problem from William J. Gilbert's "An Introduction To Mathematical Thinking: Algebra and Number Systems". Specifically, this is from Problem Set 2 ...
4
votes
3answers
121 views

How many numbers $k$ of $200 \choose k$ are divisible by $3$? $k \in \{0,1,2,\cdots 200\}$

"How many of the numbers (200 Choose k), where k is an element of the set {0,1,2,3,4,....,200} are divisible by 3? " Here is my thinking: (200 Choose 0,1, and 2) are not multiples of 3 but every ...
4
votes
5answers
154 views

If $\gcd(a,b)=1$ then, $\gcd(a^2,b^2)=1$ [duplicate]

Prove or disprove 'If $\gcd(a,b)=1$ then, $\gcd(a^2,b^2)=1$, with $a,b\not= 0$' I need to prove this statement. I think it is true and also the converse is true. I took some examples such as ...
-1
votes
1answer
53 views

Proof by induction and divisibility $21 | (4^{n+1} + 5^{2n-1}) $ [duplicate]

Prove by induction: $21 | (4^{n+1} + 5^{2n-1}) $ Skipping through the basis and onto the induction: $4\cdot 4^{n+1}+5^2 \cdot 5^{2n-1}=21a $ for some integer $a$ The following steps were: ...
1
vote
5answers
147 views

$2730\mid n^{13}-n\;\;\forall n\in\mathbb{N}$

Show that $2730\mid n^{13}-n,\;\;\forall n\in\mathbb{N}$ I tried, $2730=13\cdot5\cdot7\cdot2$ We have $13\mid n^{13}-n$, by Fermat's Little Theorem. We have $2\mid n^{13}-n$, by if $n$ even ...
0
votes
2answers
34 views

If u|s and v|t and gcd(s,t) = 1 then gcd(u,v) = 1

Proposition 1. If $\def\divides\mathrel{|}u \divides s$ and $v \divides t$ and $\gcd(s,t) = 1$ then $\gcd(u,v) = 1$. Solution. Assume $u \divides s$ and $v \divides t$. Since $\gcd(u, v) \divides u$, ...
2
votes
1answer
117 views

Proof Without Words for $GCD(a,b) \cdot LCM(a,b)=ab$

Is there any proof without words for the identity $GCD (a,b) \cdot LCM(a,b)=ab$ ?
0
votes
3answers
134 views

I need to prove only by contradiction: For $n\in \mathbb N, \; 4|(5^{n}-1)$ [closed]

suppose $n$ is a natural number. prove that: $4|(5^{n}-1)$ . I need to prove by contradiction.
3
votes
1answer
275 views

Show that if $a$ and $b$ are positive integers then $(a, b) = (a + b, [a, b])$.

Show that if $a$ and $b$ are positive integers then $(a, b)=(a + b, [a, b])$. I was thinking that since $[a, b]=LCM(a, b)=\frac{ab}{(a, b)}$ that if $d= (a + b, [a, b])$, then $d|[a,b]$ and thus ...
0
votes
3answers
407 views

Show that if a, b and c are integers with c|ab then c|(a,c)(b,c)

Show that if a, b and c are integers with c|ab then c|(a,c)(b,c) Now (a, c) and (b, c) would both divide c since it's the gcd, but how would I show c divides their product, and (a,c)(b, c) $>=$ c ...
0
votes
1answer
126 views

For natural numbers $a$ and $b$, show that $a \Bbb Z + b \Bbb Z = \gcd(a, b)\Bbb Z $

For natural numbers $a$ and $b$, show that $a \Bbb Z + b \Bbb Z = \gcd(a, b)\Bbb Z $ I just basically said that the gcd of a and b { written as C } obviously divides aZ and bZ, therefore it can be ...
0
votes
0answers
34 views

Question about zero-divisors , rings and polynomials.

Let $i,n,m$ be positive integers. For every nonnegative integer $k<i+1$ , let $a_k$ be elements of a ring $A$ that satisfies : $1)$ The ring $A$ is isomorphic to ${\Bbb R}^{n}\times{\Bbb ...
0
votes
0answers
43 views

Proof that $ k^2<2^k$ [duplicate]

I'm struggling with this problem of proof by induction: For any natural number $k\geq 5$, prove that $k^2<2^k$. I assumed that $k^2<2^k$ I want to show that $(k+1)^2<2^{k+1}$ The ...