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

learn more… | top users | synonyms

60
votes
5answers
9k 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$$
12
votes
3answers
732 views

Divisibility for 7

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 = ...
25
votes
9answers
5k views

Why $a^n - b^n$ is 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$ ...
14
votes
7answers
11k 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 ...
6
votes
2answers
859 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 ...
10
votes
5answers
401 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 ...
6
votes
3answers
8k 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?
13
votes
17answers
10k views

How to Prove the divisibility rule for $3$

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 ...
2
votes
2answers
144 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 ...
57
votes
7answers
8k views

What makes $9$ special?

I don't know if this is a well know 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 there ...
25
votes
11answers
8k views

Division of Factorials

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!)} ...
10
votes
4answers
484 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}$).
4
votes
3answers
828 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 ...
2
votes
3answers
2k 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 ...
4
votes
2answers
376 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\\ ...
11
votes
2answers
3k views

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

Possible Duplicate: Number theory proving question? Dear friends, Since $b$, $x$, $y$, $z$, $\ldots$ are integers greater than 1, how can we prove that $$ \gcd (b ^ x - 1, b ^ y - 1, b ^ ...
8
votes
5answers
498 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 ...
23
votes
6answers
16k views

If $a^2$ divides $b^2$, then $a$ divides $b$

Let $a$ and $b$ be positive integers. Prove that: If $a^2$ divides $b^2$, then $a$ divides $b$. Context: the lecturer wrote this up in my notes without proving it, but I can't seem to figure out ...
5
votes
1answer
176 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 .
10
votes
3answers
205 views

Showing that $a^n - 1 \mid a^m - 1 \iff n \mid m$

Let $a\ge 2$ be an integer. Show that for positive integers $m,n$, we have $a^n - 1$ divides $a^m - 1$ if and only if $n$ divides $m$. I am having trouble showing this. I've seen a similar ...
2
votes
4answers
541 views

Prove that $(ma, mb) = |m|(a, b)$

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 ...
12
votes
5answers
4k 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. ...
2
votes
2answers
7k 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 ...
6
votes
3answers
841 views

Why (directly!) does every number divide 9, 99, 999, … or 10, 100, 1000, …, or their product?

A curiosity that's been bugging me. More precisely: Given any integers $b\geq 1$ and $n\geq 2$, there exist integers $0\leq k, l\leq b-1$ such that $b$ divides $n^l(n^k - 1)$ exactly. The ...
5
votes
6answers
2k views

Prove that $(a-b) \mid (a^n-b^n)$

I'm trying to prove by induction that for all $a,b \in \mathbb{Z}$ and $n \in \mathbb{N}$, that $(a-b) \mid (a^n-b^n)$. The base case was trivial, so I started by assuming that $(a-b) \mid (a^n-b^n)$. ...
5
votes
5answers
5k views

Simple Proof by induction: “9 divides $n^3 + (n+1)^3 + (n+2)^3$”

I'm trying to prove using induction that 9 divides $n^3 + (n+1)^3 + (n+2)^3$ whenever $n$ is a non-negative integer. So far, I have: Base case: P(1) = (1) + (8) + (27) = 36, 36 can be divided by 9 ...
7
votes
7answers
12k 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.
9
votes
1answer
965 views

If $\gcd(a,b)=d$, then $\gcd(ac,bc)=cd$?

$A$ an integral domain, $a,b,c\in A$. If $d$ is a greatest common divisor of $a$ and $b$, is it true that $cd$ is a greatest common divisor of $ca$ and $cb$? I know it is true if $A$ is a UFD, but ...
6
votes
6answers
6k views

Prove $\gcd(a+b, a-b) = 1$ or $\gcd(a+b, a-b) = 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) ...
11
votes
6answers
6k views

How can I prove that $n^7 - n$ is divisible by $42$ for any integer $n$?

I can see that this works for any integer $n$, but I can't figure out why this works, or why the number $42$ has this property.
1
vote
6answers
5k views

suppose $\gcd(a,b)= 1$ and $a$ divides $bc$. Show that $a$ must divide $c$.

Well I thought this is obvious. since $\gcd(a,b)=1$, then we have that $a$ does not divide $b$ AND $a$ divides $bc$. this implies that $a$ divides $c$. done. but apparently this is wrong. help ...
1
vote
1answer
265 views

How to prove Greatest Common Divisor using Bézout's Lemma

The problem is to prove the following If $\gcd(a,b) = c$, then $\gcd(a^m, b^m) = c^m$ I know that this can be solved easily by proving that $c\mid a \implies c^m \mid a^m$ and $c\mid b \implies ...
1
vote
5answers
84 views

Prove if $a\mid b$ and $b\mid a$, then $|a|=|b|$ , $a, b$ are integers.

Form the assumption, we can say $b=ak$ ,$k$ integer, $a=bm$, $m$ integer. Intuitively, this conjecture makes sense. But I can't make further step.
25
votes
5answers
822 views

Prove $n\mid \phi(2^n-1)$

If $2^p-1$ is a prime, (thus $p$ is a prime, too) then $p\mid 2^p-2=\phi(2^p-1).$ But I find $n\mid \phi(2^n-1)$ is always hold, no matter what $n$ is. Such as $4\mid \phi(2^4-1)=8.$ If we denote ...
7
votes
3answers
704 views

Proof of Wolstenholme's theorem

According to the theorem, if $$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\cdots+\frac{1}{p-1} =\frac{r}{q}$$ then we have to prove that $r\equiv0 \pmod{p^2}$. (Given $p>3$, otherwise ...
12
votes
7answers
687 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.
10
votes
3answers
487 views

If $R$ is a commutative ring with identity, and $a, b\in R$ are divisible by each other, is it true that they must be associates?

Thank you very much! My problem is: If $R$ is a commutative ring with identity, and $a, b$ are its elements that are divisible by each other, is it true that they must be associates? Here, $a$ ...
6
votes
8answers
387 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 ...
2
votes
4answers
602 views

Divisibility and the Fibonacci sequence

While studying the Fibonacci sequence I encountered this problem in the handout, and I can not understand how to do it. Show that if the Fibonacci sequence has a term divisible by a natural number ...
1
vote
7answers
817 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 ...
6
votes
3answers
2k views

Prove that every positive integer $n$ is a unique product of a square and a squarefree number

I am trying to prove that for every integer $n \ge 1$, there exists uniquely determined $a > 0$ and $b > 0$ such that $n = a^2 b$, where $b$ is squarefree. I am trying to prove this using the ...
-1
votes
2answers
219 views

Divisibility of prime numbers

I have this exercise in my worksheet in the discrete mathematics course.I don't understand the part that deals with prime numbers in integer-divisibility. "Show that for a prime number $p$, if a ...
94
votes
8answers
13k views

Are half of all numbers odd?

Plato puts the following words in Socrates' mouth in the Phaedo dialogue: I mean, for instance, the number three, and there are many other examples. Take the case of three; do you not think it may ...
9
votes
3answers
2k views

Divisibility rules and congruences

Sorry if the question is old but I wasn't able to figure out the answer yet. I know that there are a lot of divisibility rules, ie: sum of digits, alternate plus and minus digits, etc... but how can ...
9
votes
12answers
5k 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 ...
9
votes
2answers
3k views

Divisibility Rules for Bases other than $10$

I still remember the feeling, when I learned that a number is divisible by $3$, if the digit sum is divisible by $3$. The general way to get these rules for the regular decimal system is ...
5
votes
5answers
2k views

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

Prove if $p$ is a prime then $p \,| \binom{p}{k}$ for $k\in\{1,\ldots,p-1\}$ I don't really know where to begin with this one.
15
votes
7answers
726 views

$n^5-n$ is divisible by $10$?

I was trying to prove this, and I realized that this is essentially a statement that $n^5$ has the same last digit as $n$, and to prove this it is sufficient to calculate $n^5$ for $0-9$ and see that ...
5
votes
2answers
4k 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 ...
1
vote
4answers
185 views

$(a^{n},b^{n})=(a,b)^{n}$ and $[a^{n},b^{n}]=[a,b]^{n}$?

How to show that $$(a^{n},b^{n})=(a,b)^{n}$$ and $$[a^{n},b^{n}]=[a,b]^{n}$$ without using modular arithmetic? Seems to have very interesting applications.$$$$Try: $(a^{n},b^{n})=d\Longrightarrow ...