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

learn more… | top users | synonyms

4
votes
4answers
1k views

Proving that $ \gcd(a,b) = as + bt $, i.e., $ \gcd $ is a linear combination. [duplicate]

For any nonzero integers $ a $ and $ b $, there exist integers $ s $ and $ t $ such that $ \gcd(a,b) = as + bt $. Moreover, $ \gcd(a,b) $ is the smallest positive integer of the form $ as + bt $. I ...
2
votes
2answers
91 views

cancelling out before evaluation of variable

I'm been working on a theory, though my math is weak. Let's say I've managed to determine that I can arrive at an answer A by always using the formula BCD / D. Of ...
-1
votes
2answers
259 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 $...
98
votes
8answers
14k 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 ...
45
votes
8answers
5k views

What is $\gcd(0,0)$?

What is the greatest common divisor of $0$ and $0$? On the one hand, Wolfram Alpha says that it is $0$; on the other hand, it also claims that $100$ divides $0$, so $100$ should be a greater common ...
10
votes
2answers
338 views

Prove that $\gcd(3^n-2,2^n-3)=\gcd(5,2^n-3)$

Prove that $\gcd(3^n-2,2^n-3)=1$ if and only if $\gcd(5,2^n-3)=1$ where $n$ is a natural number. I didn't see an easy way to prove this using the Euclidean algorithm, but it seems true that both gcd'...
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 ...
6
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.
1
vote
4answers
542 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 ...
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 $s,t$ ...
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 asked/...
10
votes
3answers
465 views

Does $a^n \mid b^n$ imply $a\mid b$?

Does $a^n \mid b^n$ imply $a\mid b$? I think it does but haven't been able to prove it. I don't know much number theory so an elementary answer would be great.
15
votes
7answers
735 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
3answers
5k views

If $2^n - 1$ is prime from some integer $n$, prove that n must also be prime.

I understand the idea of the proof. I just want to make sure I wrote my proof well. Suppose $n$ is not prime. Then $\exists x,y \in \mathbb{Z}$ such that $n = xy$. $2^{xy} - 1 = (2^x)^y - 1$ $ = (2^...
4
votes
1answer
4k views

Sum of GCD(k,n)

I want to find this $$ \sum_{k=1}^n \gcd(k,n)$$ but I don't know how to solve. Does anybody can help me to finding this problem. Thanks.
2
votes
2answers
140 views

$ 1^k+2^k+3^k+…+(p-1)^k $ always a multiple of $p$?

I would appreciate if somebody could help me with the following problem: Q: For any prime number $p(p\geq 3), k=1,2,3,...,p-2$, why is $$ 1^k+2^k+3^k+...+(p-1)^k $$ always a multiple of $p$ ?
1
vote
1answer
73 views

Is it possible to find $n-1$ consecutive composite integers

Given an integer $n\geq 2$ ,can we always find an integer $m$ such that each of the $n-1$ consecutive integers $m+2,m+3,.....,m+n$ are composite?
1
vote
3answers
82 views

If $\gcd (a,b) = 1$, what can be said about $\gcd (a+b,a-b)$?

Suppose $a, b \in \mathbb{Z}$, $a > b$, and $\gcd (a,b) = 1$. What can be said about $\gcd (a+b,a-b)$? Is it true in general that $\gcd (a+b,a-b) \leq 2$?
5
votes
3answers
2k views

Show that $\gcd(a,bc)=1$ if and only if $\gcd(a,b)=1$ and $\gcd(a,c)=1$

Show that $\gcd(a,bc)=1$ if and only if $\gcd(a,b)=1$ and $\gcd(a,c)=1$. I am new at proofs and I think I should use Euclid's Lemma which states "If $p$ is a prime that divides $ab$, then $p$ divides ...
5
votes
3answers
548 views

Prove that $(a+1)(a+2)…(a+b)$ is divisible by $b!$ [duplicate]

The problem is following, prove that: $$(a+1)(a+2)...(a+b)\text{ is divisible by } b!\text{ for every positive integer a,b}$$ I've tried solving this problem using mathematical induction, but I ...
3
votes
6answers
324 views

Prove that $6$ divides $n(n + 1)(n + 2)$

I am stuck on this problem, and was wondering if anyone could help me out with this. The question is as follows: Let $n$ be an integer such that $n ≥ 1$. Prove that $6$ divides $n(n + 1)(n + 2)$. ...
3
votes
4answers
655 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 ...
2
votes
3answers
90 views

Proof that if $\gcd(a,b) = 1$ and $a\mid n$ and $b\mid n$, $ab \mid n$

I'm learning about properties of greatest common divisors, specifically when two numbers are relatively prime. The exercise I'm working through is : Suppose that $\gcd(a,b) = 1$ and that $a\mid n$...
44
votes
4answers
2k views

How does the divisibility graphs work?

I came across this graphic method for checking divisibility by $7$. $\hskip1.5in$ Write down a number $n$. Start at the small white node at the bottom of the graph. For each digit $d$ in $...
25
votes
8answers
647 views

Prove that $(mn)!$ is divisible by $(n!)\cdot(m!)^n$

Prove that $$(n!)\cdot(m!)^n|(mn)!$$ I can prove it using Legendre's Formula, but I have to use the lemma that $$ \dfrac{\displaystyle\left(\sum_{i=1}^na_i\right)!}{\displaystyle\prod_{...
18
votes
2answers
508 views

Do there exist two primes $p<q$ such that $p^n-1\mid q^n-1$ for infinitely many $n$?

We can prove that there is no integer $n>1$ such that $2^n-1\mid 3^n-1$. This leads to the following question: Is it true that for every pair of primes $p<q$ there are only finitely many ...
13
votes
2answers
2k views

Elementary proof of Zsigmondy's theorem

I've been writing a not-so-short introduction to elementary number theory, supplying proofs for all theorems. When coming across Zsigmondy's theorem, it seemed difficult to find a proof available on ...
18
votes
3answers
1k views

Proving there are an infinite number of pairs of positive integers $(m,n)$ such that $\frac{m+1}{n}+\frac{n+1}{m}$ is a positive integer

The question is: Show that there are an infinite number of pairs $(m,n): m, n \in \mathbb{Z}^{+}$, such that: $$\frac{m+1}{n}+\frac{n+1}{m} \in \mathbb{Z}^{+}$$ I started off approaching this ...
11
votes
2answers
511 views

How does one attack a divisibility problem like $(a+b)^2 \mid (2a^3+6a^2b+1)$?

In my current line of investigation, I am running into [many] divisibility questions like the one in the title, i.e. $$ (a+b)^2 \mid (2a^3+6a^2b+1), \qquad(\star) $$ where $a > b \ge 1$ are ...
7
votes
3answers
800 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 $1+\...
4
votes
1answer
285 views

Divisibility of $2^n - 1$ by $2^{m+n} - 3^m$.

For what values of $m,n$ natural, do $2^n - 1$ is divisible by $2^{m+n} - 3^m$? Thank you very much.
13
votes
6answers
2k views

Proof: if $p$ is prime, and $0<k<p$ then $p$ divides $\binom pk$ [duplicate]

Question : If $p$ is prime, and $0< k< p$ show that $ p \mid {p \choose k}$ ${p \choose k}$ can be rewritten as: $${p(p-1)(p-2)\dots(p-(k-1))(p-k)! \over (p-k)!\cdot k(k-1)(k-2)\dots3\cdot2\...
7
votes
2answers
370 views

Prove Divisibility In Fibonacci Sequence Over A Prime Number

In The Fibonacci sequence which is defined as $$ F_n=F_{n-1}+F_{n-2}, $$ lets say we have the number $p$ which is an odd prime. Prove that: $F_{p-1} + F_{p+1} -1$ Is divisible by $p$. Prove that ...
2
votes
4answers
177 views

Division of $q^n-1$ by $q^m-1$, in Wedderburn's theorem

I need this for a proof of Wedderburn's theorem: $$q^m - 1 | q^n - 1 \quad \Rightarrow \quad m|n$$ with $q>1 \in \mathbf{N}$ and $m,n \in \mathbf{N}$. I'd also like to know if it works the other ...
7
votes
2answers
206 views

$n\mid \phi(a^{n}-1)$ for any $a>n$?

I saw the proof which goes as follows: $a^{n} \equiv 1 \pmod{a^{n}-1} $, and $n$ is the smallest power of a such that this is true. We also know that by Euler's Identity $a^{\phi(a^{n}-1)}\equiv 1\...
3
votes
1answer
109 views

Determine the divisibility of a given number without performing full division

My question is slightly more complicated than what's implied on the title, so I will start with an example. Given any number $N$ on base $10$, we can easily determine whether or not $N$ is divisible ...
2
votes
3answers
128 views

Divisor in $\mathbb{C}[X]$ $\implies$ divisor in $\mathbb{R}[X]$?

let $P \in \mathbb{R}[X]$ be a real polynomial divisible by a polynomial $Q \in \mathbb{R}[X]$ in $\mathbb{C}[X]$. How can I easily show that $P$ is also divisible by $Q$ in $\mathbb{R}[X]$? A simple ...
2
votes
3answers
606 views

Prove that distinct Fermat Numbers are relatively prime [duplicate]

The Fermat numbers are defined by $F_m = 2^{2^m} + 1$. Prove that for $m \ne n$ we have $(F_m, F_n) = 1$. I have to first prove that $F_{m+1} = F_0F_1 \cdots F_m + 2$ by representing $F_{m+1}$ in ...
1
vote
4answers
216 views

If $\gcd(a,n) = 1$ and $\gcd(b,n) = 1$, then $\gcd(ab,n) = 1$.

If $\gcd(a,n) = 1$ and $\gcd(b,n) = 1$, then $\gcd(ab,n) = 1$. Also... $a,b$ and $n$ are natural numbers. I feel I should begin with EEA to multiply out the gcd's, but I don't know where to go from ...
6
votes
4answers
3k views

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

Assuming that $\gcd(a,b) = 1$, prove that $\gcd(a+b,a^2+b^2) = 1$ or $2$. I tried this problem and ended up with $$d\mid 2a^2,\quad d\mid 2b^2$$ where $d = \gcd(a+b,a^2+b^2)$, but then I am stuck; ...
5
votes
4answers
4k views

How to prove gcd of consecutive Fibonacci numbers is 1? [duplicate]

Possible Duplicate: Prove that two any consecutive terms of Fibonacci sequence are relatively prime How to prove it ? Can you help me ? Let $f_n$ be Fibonacci Sequence. $$(f_{n},f_{n+1})=1,\...
5
votes
7answers
337 views

Prove that if $n^2$ is divided by 3, then also $n$ can also be divided by 3.

$n\in \Bbb N$ Prove that if $n^2$ is divided by 3, then also n can also be divided by 3. I started solving this by induction, but I'm not sure that I'm going in the right direction, any ...
3
votes
2answers
98 views

Prove that $\gcd(a^2, b^2) = \gcd(a, b)^2$ [duplicate]

The problem's quite clear. Prove that $$\gcd(a^2, b^2) = \gcd(a, b)^2$$ This is easy to understand intuitively and using the Fundamental Theorem of Arithmetic would be easy but I want to prove it by ...
2
votes
3answers
135 views

Let $a,b$ be positive integers such that $a\mid b^2 , b^2\mid a^3 , a^3\mid b^4 \ldots$ so on , then $a=b$?

Let $a,b$ be positive integers such that $a\mid b^2 , b^2\mid a^3 , a^3\mid b^4 \ldots$ that is $a^{2n-1}\mid b^{2n} ; b^{2n}\mid a^{2n+1} , \forall n \in \mathbb Z^+$ , then is it true that $a=b$ ?
1
vote
2answers
766 views

Show that if $a$ and $b$ are positive integers with $(a,b)=1$ then $(a^n, b^n) = 1$ for all positive integers n [duplicate]

Show that if $a$ and $b$ are positive integers with $(a,b)=1$ then $(a^n, b^n) = 1$ for all positive integers n Hi everyone, for the proof to the above question, Can I assume that since $(a, b) = 1$,...
0
votes
3answers
1k views

How to show that $\gcd(n! + 1, (n + 1)! + 1) \mid n$?

Let $n$ be a positive integer, $n!$ denotes the factorial of $n$. Let $d = \gcd(n! + 1, (n + 1)! + 1)$. Show that $d$ divides $n$. (Hint: notice that $(n+1)(n!+1) = (n+1)!+n+1$)
6
votes
2answers
143 views

Prove or disprove : $a^3\mid b^2 \Rightarrow a\mid b$

I think it's true, because I can't see counterexamples. Here's a proof that I am not sure of: Let $p_1,p_2,\ldots, p_n$ be the prime factors of $a$ or $b$ \begin{eqnarray} a&=& p_1^{\...
5
votes
5answers
1k views

Prove 24 divides $u^3-u$ for all odd natural numbers $u$

At our college, a professor told us to prove by a semi-formal demonstration (without complete induction): For every odd natural: $24\mid(u^3-u)$ He said that that example was taken from a high ...
5
votes
5answers
998 views

Prove by induction that $2^{2n} – 1$ is divisible by $3$ whenever n is a positive integer.

I am confused as to how to solve this question. For the Base case $n=1$, $(2^{2(1)} - 1)\,/\, 3 = 1$, base case holds My induction hypothesis is: Assume $2^{2k} -1$ is divisible by $3$ when $k$ is a ...
5
votes
1answer
9k views

Prove by mathematical induction that $n^3 - n$ is divisible by $3$ for all natural number $n$

I'm working on a task where I'm a bit unsure if the answer I've got is correct. Here is the task: Show by induction that the following assertion is true for all natural numbers $n$ $n^3 - ...