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

learn more… | top users | synonyms

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 ...
62
votes
13answers
31k views

Dividing 100% by 3 without any left

In mathematics, as far as I know, you can't divide 100% by 3 without having 0,1...% left. Imagine an apple which was cloned two times, so the other 2 are completely equal in 'quality'. The totality ...
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$$
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 ...
43
votes
8answers
4k 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 ...
43
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 ...
36
votes
5answers
6k views

If a prime number is reversed, and then appended to itself, why is the result always a composite number?

$2 \Rightarrow 22$ which is a composite number. $37 \Rightarrow 3773$ which is a composite number. $523 \Rightarrow 523325$ which is a composite number. $8123 \Rightarrow 81233218$ which is a ...
35
votes
3answers
771 views

Prove that there exist infinitely many integers $(n^{2015}+1)\mid n!$

I conjecture that there exist infinitely many integers $n$ such that $$(n^{2015}+1)\mid n!.$$ I have seen a simpler problem that there exist infinitely many integers $n$ such that $(n^2+1)\mid ...
29
votes
10answers
5k views

How to prove that all odd powers of two add one are multiples of three

For example \begin{align} 2^5 + 1 &= 33\\ 2^{11} + 1 &= 2049\ \text{(dividing by $3$ gives $683$)} \end{align} I know that $2^{61}- 1$ is a prime number, but how do I prove that ...
27
votes
0answers
352 views

Fractals using just modulo operation

Let us calculate the remainder after division of $27$ by $10$. $27 \equiv 7 \pmod{10}$ We have $7$. So let's calculate the remainder after divison of $27$ by $7$. $ 27 \equiv 6 \pmod{7}$ Ok, so ...
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!)} ...
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$ ...
25
votes
5answers
824 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 ...
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 ...
22
votes
10answers
1k views

Prove if $56x = 65y$ then $x + y$ is divisible by $11$

If $x$ and $y$ are natural numbers, and $56x = 65y$, prove that $x + y$ is divisible by $11$. I tried taking the $\gcd(56x,65y)$ using the Euclidean algorithm, but I got nowhere with it and do not ...
20
votes
1answer
490 views

Is $\sum_{k=1}^{n} k^k / \sum_{k=1}^{n} k \in \mathbb{N}$ for some $n > 1$?

Let $ A = \sum_{k=1}^{n} k^k $ and $ B = \sum_{k=1}^{n} k$, where $n >1 $ is a positive integer. Is $A/B$ ever an integer?
19
votes
4answers
2k views

Is the number $333{,}333{,}333{,}333{,}333{,}333{,}333{,}333{,}334$ a perfect square?

I know that if the number is a perfect square then it will be congruent to $0$ or $1$ (mod $4$). Now since the number is even, I know that it is either $0$ or $2$ (mod $4$). How would I go about ...
19
votes
5answers
1k views

How does one show that two general numbers $n! + 1$ and $(n+1)! + 1$ are relatively prime?

How does one show that two general numbers $n! + 1$ and $(n+1)! + 1$ are relatively prime? I don't mind if someone uses a different example, I want to learn how to prove this class of problems. My ...
19
votes
3answers
2k views

Prove that there exists a number divisible by 1999 with digit sum 1999

My nephew in the secondary school asked me how to solve the problem as stated in the title. Honestly, I do not have any idea how to do it: Prove that there exists a positive integer number such ...
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 ...
18
votes
3answers
970 views

Proof by induction that $n^3 + (n + 1)^3 + (n + 2)^3$ is a multiple of $9$. Please mark/grade.

What do you think about my first induction proof? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof First, introducing a predicate ...
18
votes
2answers
483 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 ...
17
votes
4answers
396 views

Prove that $\dfrac{(n^2)!}{(n!)^n}$ is an integer for every $n \in \mathbb{N}$

Prove that $\dfrac{(n^2)!}{(n!)^n}$ is an integer for every $n \in \mathbb{N}$ I know that there are tools in Number theory to proves the required but I want to use the tool that says that if you ...
17
votes
4answers
497 views

Do there exist infinitely many pairs of primes $(p,q)$ such that $pq$ divides $2^{p-1}+2^{q-1}-2$?

A mathematician friend gave me this question (partly as a joke) a few months ago and it has puzzled me for a long time:- Do there exist infinitely many pairs of primes $(p,q)$ such that ...
16
votes
6answers
274 views
+200

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 $$ ...
15
votes
7answers
727 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 ...
15
votes
6answers
2k views

Divisibility criteria of 24. Why is this?

I am currently familiar with the method of checking if a number is divisible by $2, 3, 4, 5, 6, 8, 9, 10, 11$. While Checking for divisibility for $24$ (online). I found out that the number has to ...
14
votes
14answers
2k views

How to prove that $k^3+3k^2+2k$ is always divisible by $3$? [closed]

How can I prove that the following polynomial expression is divisible by 3 for all integers $k$? $$k^3 + 3k^2 + 2k$$
14
votes
6answers
3k views

Is an arbitrary number of the form xyzxyz divisible by 7, 11, 13?

So I was given this question Choose any 3-digit number xyz and write it after itself as follows: xyzxyz. Check whether it is divisible by 7,11, 13. Is an arbitrary number of the form xyzxyz ...
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 ...
14
votes
1answer
741 views

My attempt to prove GCD exists

Please review my attempt to prove a theorem. Any mistakes you point would be highly appreciated by me. To prove the theorem, I'll be using the following properties which I'm assuming have already ...
14
votes
1answer
508 views

My first proof that uses the well-ordering principle (very simple number theory). Please mark/grade.

What do you think about my first proof that uses the well-ordering principle? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof ...
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 ...
13
votes
2answers
305 views

Prove $6 \nmid [\left( \sqrt[3]{28} - 3 \right)^{-n}]$

Prove that: $$6 \not\left|\ \left\lfloor\frac 1 {(\sqrt[3]{28} - 3)^{n}}\right\rfloor \ (n \in Z^+)\right.$$ ($\lfloor x\rfloor$ = largest integer not exceeding $x$) I am very bad as English and ...
13
votes
3answers
160 views

Can exist an even number greater than $36$ with more even divisors than $36$, all of them being a prime$-1$?

I did a little test today looking for all the numbers such as their even divisors are exactly all of them a prime number minus 1, to verify possible properties of them. These are the first terms, it ...
13
votes
3answers
138 views

Generating numbers by repeated doubling and digit reversal

Let $S$ be the smallest set of positive integers satisfying the following conditions: $1 \in S$, If $n \in S$ then $2n \in S$, If $n \in S$ then the digit reversal of $n$ is also in $S$. We assume ...
12
votes
2answers
1k views

What is the remainder when $1! + 2! + 3! +\cdots+ 1000!$ is divided by $12$?

What is the remainder when $$1! + 2! + 3! +\cdots+ 1000!$$ is divided by $12$. I have tried to find the answer using the Binomial Theorem but that doesn't help. How will we do this? Please help.
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. ...
12
votes
6answers
712 views

Is 1100 a valid state for this machine?

A room starts out empty. Every hour, either 2 people enter or 4 people leave. In exactly a year, can there be exactly 1100 people in the room? I think there can be because 1100 is even, but how do I ...
12
votes
7answers
690 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.
12
votes
4answers
2k views

Showing $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, or $9$

Given that n is a positive integer show that $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, or $9$. I'm thinking that I should be using the property of gcd that says if a and b are integers then gcd(a,b) = ...
12
votes
2answers
454 views

How rare are the primes $p$ such that $p$ divides the sum of all primes less than $p$?

This is just for fun! The title pretty much says it all. It's probably a very difficult question. Up to the $40,000^{th}$ prime $(479909)$, I have found only $5$, $71$ and $369119$ with this ...
12
votes
3answers
417 views

Mental Primality Testing

At a trivia night, the following question was posed: "What is the smallest 5 digit prime?" Teams (of 4) were given about a minute to write down their answer to the question. Obviously, the answer is ...
12
votes
3answers
735 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 = ...
12
votes
6answers
1k 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 ...
12
votes
2answers
1k 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 ...
12
votes
2answers
490 views

Show divisibility by 7

I was stuck at this question: Suppose $a^2+b^2=c^2$ for $a,b,c \in \mathbb Z$, and neither $a$ nor $b$ is a multiple of 7. Show that $a^2-b^2$ is a multiple of 7 I tried to write $b^2$ as ...
12
votes
1answer
207 views

Family of GCDs all equal to $2$

Is it true that $$\gcd\left(5^{2^n} + 1, 13^{2^n} + 1\right) = 2$$ for all $n \in \mathbf{Z}_{\geq 0}$? I'm continually stumped with this and verifying it numerically is quite expensive very ...
12
votes
2answers
185 views

Prove that neither $A$ nor $B$ is divisible by $5$

Let the sum $$ {1+ \frac12 + \frac13 + \frac 14+ \dots +\frac1{99} + \frac 1{100}}$$ be written as $\frac AB$, where $A$ and $B$ are positive integers with no common factors. Show that neither $A$ ...
12
votes
1answer
171 views

Does there always exist an even $m$ that is a multiple of exactly $n$ of the numbers $1$, $2$, …, $2n$?

Let $n>1$ be a positive integer. Then there exists a positive integer $m$ such that exactly half of the numbers $1$, $2$, $\ldots$, $2n$ divides $m$: one can take $m = (2n-1)!! = (2n-1) \times ...