Questions tagged [divisibility]

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

Filter by
Sorted by
Tagged with
88
votes
9answers
6k views

Divisibility by 7 rule, and Congruence Arithmetic Laws

I have seen other criteria for divisibility by 7. Criterion described below present in the book Handbook of Mathematics for IN Bronshtein (p. 323) is interesting, but could not prove it. Let $n = (...
142
votes
7answers
30k views

Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$

For all $a, m, n \in \mathbb{Z}^+$, $$\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$$
40
votes
8answers
16k views

Why is $a^n - b^n$ divisible by $a-b$?

I did some mathematical induction problems on divisibility $9^n$ $-$ $2^n$ is divisible by 7. $4^n$ $-$ $1$ is divisible by 3. $9^n$ $-$ $4^n$ is divisible by 5. Can these be generalized as $a^n$ $-$...
38
votes
7answers
37k views

The product of $n$ consecutive integers is divisible by $n$ factorial

How can we prove that the product of $n$ consecutive integers is divisible by $n$ factorial? Note: In this subsequent question and the comments here the OP has clarified that he seeks a proof that "...
67
votes
7answers
11k views

Why $9$ & $11$ are special in divisibility tests using decimal digit sums? (casting out nines & elevens)

I don't know if this is a well-known fact, but I have observed that every number, no matter how large, that is equally divided by $9$, will equal $9$ if you add all the numbers it is made from until ...
29
votes
4answers
6k views

If $a \mid m$ and $(a + 1) \mid m$, prove $a(a + 1) | m$.

Can anyone help me out here? Can't seem to find the right rules of divisibility to show this: If $a \mid m$ and $(a + 1) \mid m$, then $a(a + 1) \mid m$.
3
votes
4answers
5k views

Prove that $(ma, mb) = |m|(a, b)\ $ [GCD Distributive Law]

I'm trying to prove that $(ma, mb) = $|$m$|$(a, b)$ , where $(ma, mb)$ is the greatest common divisor between $ma$ and $mb$. My thoughts: If $(ma, mb) = d$ , then $d$|$ma$ and $d$|$mb$ → $d$|$max +...
34
votes
8answers
16k views

Why $\gcd(qb+r,b)=\gcd(b,r)$?

Given: $a = qb + r$. Then it holds that $\gcd(a,b)=\gcd(b,r)$. That doesn't sound logical to me. Why is this so? Addendum by LePressentiment on 11/29/2013: (in the interest of http://meta.math....
17
votes
3answers
4k views

Divisibility criteria for $7,11,13,17,19$

A number is divisible by $2$ if it ends in $0,2,4,6,8$. It is divisible by $3$ if sum of ciphers is divisible by $3$. It is divisible by $5$ if it ends $0$ or $5$. These are simple criteria for ...
2
votes
3answers
1k views

Let $a$ and $b$ be non-zero integers, and $c$ be an integer. Let $d = \gcd(a, b)$. Prove that if $a|c$ and $b|c$ then $ab|cd$.

Let $a$ and $b$ be non-zero integers, and $c$ be an integer. Let $d = hcf(a, b)$. Prove that if $a|c$ and $b|c$ then $ab|cd$. We know that if $a|c$ and $b|c$ then $a\cdot b\cdot s=c$ (for some ...
83
votes
20answers
52k views

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

Let $p>3$ be a prime. Prove that $24 \mid p^2-1$. 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 ...
9
votes
5answers
12k views

$\gcd(a,b,c)=\gcd(\gcd(a,b),c)\,$ [GCD Associative Law]

Prove $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ for $0\ne a,b,c\in \Bbb{Z}$. I tried solving it with sets but I sense there are some details I am missing. I would truly appreciate your reference.
29
votes
5answers
9k views

Fibonacci divisibilty properties $ F_n\mid F_{kn},\,$ $\, \gcd(F_n,F_m) = F_{\gcd(n,m)}$

Can any one give a generalization of the following properties in a single proof? I have checked the results, which I have given below by trial and error method. I am looking for a general proof, which ...
60
votes
7answers
8k views

Polynomial division: an obvious trick? [reducing mod $\textit{simpler}$ multiples]

The following question was asked on a high school test, where the students were given a few minutes per question, at most: Given that, $$P(x)=x^{104}+x^{93}+x^{82}+x^{71}+1$$ and, $$Q(x)=x^4+...
12
votes
5answers
2k views

Show that $\gcd\left(\frac{a^n-b^n}{a-b},a-b\right)=\gcd(n d^{n-1},a-b)$

How to show that $$ \gcd\bigg( {a^n-b^n \over a-b} ,a-b\bigg )=\gcd(n d^{n-1},a-b ) $$ $a,b\in \mathbb Z$ where $d=\gcd(a,b)$? Note $\ $ Some of the answers below were merged from this ...
17
votes
4answers
1k views

Prove: If $\gcd(a,b,c)=1$ then there exists $z$ such that $\gcd(az+b,c) = 1$

I can't crack this one. Prove: If $\gcd(a,b,c)=1$ then there exists $z$ such that $\gcd(az+b,c) = 1$ (the only constraint is that $a,b,c,z \in \mathbb{Z}$ and $c\neq 0)$
13
votes
6answers
16k views

The product of $n$ consecutive integers is divisible by $ n!$ (without using the properties of binomial coefficients)

How can we prove, without using the properties of binomial coefficients, the product of $n$ consecutive integers is divisible by $n$ factorial?
8
votes
2answers
4k views

How to prove that $z\gcd(a,b)=\gcd(za,zb)$

I need to prove that $z\gcd(a,b)=\gcd(za,zb)$. I tried a lot, for example, looking at set of common divisors of the two sides, but I can't conclude anything from that. Can you please give me some ...
20
votes
6answers
30k views

Prove $\gcd(a+b, a-b) = 1$ or $2\,$ if $\,\gcd(a,b) = 1$

I want to show that for $\gcd(a,b) = 1$ $a,b \in Z$ $\gcd(a+b, a-b) = 1$ or $\gcd(a+b, a-b) = 2$ holds. I think the first step should look something like this: $d = \gcd(a+b, a-b) = \gcd(...
5
votes
3answers
961 views

Proving $p\nmid \binom{p^rm}{p^r}$ where $p\nmid m$

A question from Advanced Modern Algebra by Joseph J.Rotman. Let $n=(p^r)m $ such that the prime $p\nmid m$.Prove that $p\nmid \dbinom{n}{p^r}$.HINT: Assume otherwise, cross multiply and apply ...
17
votes
3answers
1k views

Are associates unit multiples in a commutative ring with $1$?

Recall the following relevant definitions. We say that $b$ is divisible by $a$ in $R$, or $a\mid b$ in $R$, if $b = r a$ for some $r\in R$. $a$ and $b$ are associates in $R$ if $a\mid b$ and $b\mid ...
4
votes
2answers
2k 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\\ 8&...
9
votes
2answers
36k views

If $\gcd(a,b)=1$ and $a$ and $b$ divide $c$, then so does $ab$

Using divisibility theorems, prove that if $\gcd(a,b)=1$ and $a|c$ and $b|c$, then $ab|c$. This is pretty clear by UPF, but I'm having some trouble proving it using divisibility theorems. I was ...
17
votes
7answers
48k views

If $\gcd(a,b)=1$ and $\gcd(a,c)=1$, then $\gcd(a,bc)=1$

How do I go about proving this? If $\gcd(a,b)=1$ and $\gcd(a,c)=1$, then $\gcd(a,bc)=1$. I'm very confused with gcd proofs.
5
votes
7answers
29k views

If $\gcd(a,b)= 1$ and $a$ divides $bc$ then $a$ divides $c\ $ [Euclid's Lemma]

Well I thought this is obvious. since $\gcd(a,b)=1$, then we have that $a\not\mid b$ AND $a\mid bc$. This implies that $a$ divides $c$. But apparently this is wrong. Help explain why this way is ...
28
votes
7answers
17k views

If $n\ne 4$ is composite, then $n$ divides $(n-1)!$.

I have a proof and need some feedback. It seems really obvious that the statement is true but it is always the obvious ones that are a little trickier to prove. So I would appreciate any feedback. ...
20
votes
5answers
9k views

Proving that $\gcd(2^m - 1, 2^n - 1) = 2^{\gcd(m,n )} - 1$

Somewhere on Stack Exchange I saw the equation $$\gcd(2^m-1,2^n-1)=2^{\gcd(m,n)}-1.$$ I had never seen this before, so I started trying to prove it. Without success... Can anyone explain me (so ...
13
votes
2answers
5k views

Derive a formula to find the number of trailing zeroes in $n!$ [duplicate]

Possible Duplicate: How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes? I know that I have to find the number of factors of $5$'s, $25$'s, $125$'s etc....
5
votes
10answers
1k views

If a prime $p\mid ab$, then $p\mid a$ or $p\mid b$

If a prime number $p$ is a divisor of a product $ab$, $p$ has to be a divisor of $b$ or $a$. How can I demonstrate this theorem? I demonstrated this theorem on one way using Bezout's theorem in an ...
36
votes
12answers
17k views

Division of Factorials [binomal coefficients are integers]

I have a partition of a positive integer $(p)$. How can I prove that the factorial of $p$ can always be divided by the product of the factorials of the parts? As a quick example $\frac{9!}{(2!3!4!)} =...
3
votes
5answers
310 views

How to prove $\,x^a-1 \mid x^b-1 \iff a\mid b$

How to prove $x^a-1\mid x^b-1 \iff a \mid b$, where $x \ge 2$ and $a,b,x \in \Bbb Z$. I've tried the following in attempting to solve this: $$a\mid b \Rightarrow aq=b \Rightarrow x^{aq}=x^b \...
16
votes
2answers
1k views

${\gcd(n,m)\over n}{n\choose m}$ is an integer

Prove that for every $n\geq m \geq1$ natural numbers, the following number is an integer: $${\gcd(n,m)\over n}\cdot{n\choose m}$$ Where $\gcd$ is the greatest common divisor. I tried to make it ...
8
votes
10answers
3k views

How to show that $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\cdot3\cdot2$ We have $13\mid n^{13}-n$, by Fermat's Little Theorem. We have $2\mid n^{13}-n$, by if $n$ even ...
19
votes
12answers
18k views

If $\gcd(a,b)=1$, then $\gcd(a^n,b^n)=1$

If $\gcd(a,b)=1$, then $\gcd(a^n,b^n)=1$ This seems clear, but I don't know how to prove this.. I was trying to show this by induction such that if $a^{n+1}$ = $rs$ and $b^{n+1}$ = $rt$, then $s,t$ ...
34
votes
17answers
61k views

How to prove the divisibility rule for $3\, $ [casting out threes]

The divisibility rule for $3$ is well-known: if you add up the digits of $n$ and the sum is divisible by $3$, then $n$ is divisible by three. This is quite helpful for determining if really large ...
16
votes
5answers
15k views

Proving prime $p$ divides $\binom{p}{k}$ for $k\in\{1,\ldots,p-1\}$

Prove if $p$ is a prime then $p \mid \binom pk$ for $k\in\{1,\ldots,p-1\}$ I don't really know where to begin with this one. I can see that I have to use the fact that $p$ is prime somewhere - the ...
3
votes
1answer
174 views

$d\mid a,b \iff d\mid\gcd(a,b) \ $ [GCD Universal Property]

I know that the definition of gcd of two numbers $ a, b $ is $G$ ,where $G\mid a$, $\;G\mid b $ and If $d\mid a$, $\;d\mid b $, then $ d\mid G.$ Now, using this how do I prove that in $\mathbb Z$, ...
17
votes
2answers
7k views

$\gcd(b^x - 1, b^y - 1, b^ z- 1,\dots) = b^{\gcd(x, y, z,\dots)} -1$ [duplicate]

Possible Duplicate: Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$ $b$, $x$, $y$, $z$, $\ldots$ are integers greater than 1. How can we prove that $$ \gcd (b ^ x - 1, b ^ y - 1, b ^ z - ...
6
votes
1answer
449 views

How can I find $\gcd(a^m+1,a^n+1)$ with $a,m,n$ positive integers?

How can I find $\gcd(a^m+1,a^n+1)$ with $a,m,n$ positive integers? I have this idea: Let $d=\gcd(m,n)$. Then there exist positive integers $x,y$ such that $mx-ny=d$ (WLOG). We shall find $G=\gcd(a^...
3
votes
4answers
6k views

GCD Proof with Multiplication: gcd(ax,bx) = x$\cdot$gcd(a,b)

I was curious as to another method of proof for this: Given $a$, $b$, and $x$ are all natural numbers, $\gcd(ax,bx) = x \cdot \gcd(a,b)$ I'm confident I've found the method using a generic common ...
14
votes
2answers
23k views

Proof of $\gcd(a,b)=ax+by$

Here is my proof of $\gcd(a,b)=ax+by$ for $a, b, x, y \in \mathbb{Z}$. Am I doing something wrong? Are there easier proofs? $a,b \in \mathbb{Z}, g=\gcd(a,b)$ and suppose $g \neq ax + by$. Let $c$ be ...
5
votes
5answers
3k views

Prove: If $a\mid m$ and $b\mid m$ and $\gcd(a,b)=1$ then $ab\mid m$

Prove: If $a\mid m$ and $b\mid m$ and $\gcd(a,b)=1$ then $ab\mid m$ I thought that $m=ab$ but I was given a counterexample in a comment below. So all I really know is $m=ax$ and $m=by$ for some $x,y ...
10
votes
1answer
802 views

$\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1$, or $p$

Let $p$ be prime number ($p\gt2$) and $a,b\in\mathbb Z$ ,$a+b\neq0$ ,$\gcd(a,b)=1$ how to prove that $$\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1~~\text{or}~~ p$$ Thanks in advance .
1
vote
2answers
880 views

Greatest common divisor is the smallest positive number that can be written as $sa+tb$

We know that $d = \gcd(a, b)$ can be written as $sa + tb$, where $s, t \in \mathbb{Z}$. Apparently, $d$ is the smallest positive number that can be written in this form. Why is this so?
44
votes
3answers
2k views

How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes? [duplicate]

Possible Duplicate: Highest power of a prime $p$ dividing $N!$ How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes?
15
votes
5answers
14k views

Show that $11^{n+1}+12^{2n-1}$ is divisible by $133$.

Problem taken from a paper on mathematical induction by Gerardo Con Diaz. Although it doesn't look like anything special, I have spent a considerable amount of time trying to crack this, with no luck. ...
15
votes
6answers
11k views

Concise proof that every common divisor divides GCD without Bezout's identity?

In the integers, it follows almost immediately from the division theorem and the fact that $a | x,y \implies a | ux + vy$ for any $u, v \in \mathbb{Z}$ that the least common multiple of $a$ and $b$ ...
6
votes
2answers
1k views

If $\gcd(a, b) = 1$, then $\gcd(ab, c) = \gcd(a, c) \cdot\gcd(b, c)$

How can I prove that if $\gcd(a, b) = 1$, then $\gcd(ab, c) = \gcd(a, c) \times \gcd(b, c)$? By eea there exists $ax+by=1$ from $\gcd(a,b)=1$ so a and be are co-primes there also exists $dk=a$ and $...
4
votes
4answers
1k views

prove that $\operatorname{lcm}(n,m) = nm/\gcd(n,m)$

I'm trying to prove that $\operatorname{lcm}(n,m) = nm/\gcd(n,m)$ I showed that both $n,m$ divides $nm/\gcd(n,m)$ but I can't prove that it is the smallest number. Any help will be appreciated.
11
votes
5answers
5k views

Fibonacci sequence divisible by 7?

Make and prove a conjecture about when the Fibonacci sequence, $F_n$, is divisible by $7$. I've realized it's when $n$ is a multiple of $8$. I just don't know how to go about proving it.

1
2 3 4 5
17