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

learn more… | top users | synonyms

96
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 ...
66
votes
5answers
10k 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$$
65
votes
14answers
34k 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 ...
58
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 ...
52
votes
16answers
16k views

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

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 I already know.
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 ...
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 ...
43
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?
37
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
786 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 ...
32
votes
0answers
470 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 ...
30
votes
10answers
6k 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 ...
29
votes
1answer
343 views

A spiralling sequence based on integer divisors. Has anyone noticed this before?

Firstly, please excuse the informal style of my explanation, as I am not a mathematician, although I am aware that this can be explained in more formal terms. I have mapped integers to points on a ...
26
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
8answers
609 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 $$ ...
25
votes
5answers
877 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 ...
25
votes
0answers
629 views

How to solve this two simultaneous “divisibilities” : $n+1\mid m^2+1$ and $m+1\mid n^2+1$

Is it possible to find all integers $m>0$ and $n>0$ such that $n+1\mid m^2+1$ and $m+1\,|\,n^2+1$ ? I succeed to prove there is an infinite number of solutions, but I can not progress ...
24
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!)} ...
23
votes
6answers
18k 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 ...
21
votes
1answer
637 views

One of any consecutive integers is coprime to the rest

After reading this question, I conjectured a generalization of it. Conjecture: Fix $k\in \mathbb N$. Then, for all $n\in \mathbb N$, one of $n+1,\ldots,n+k$ is coprime to the rest. I ...
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
990 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
505 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
403 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 ...
15
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 ...
15
votes
17answers
13k 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 ...
15
votes
7answers
730 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 ...
15
votes
1answer
753 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
7answers
12k 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
3answers
822 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 = ...
14
votes
1answer
539 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
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$$
13
votes
2answers
484 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 ...
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
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 ...
13
votes
3answers
179 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
144 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 ...
13
votes
2answers
303 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
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
736 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
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.
12
votes
7answers
746 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.