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

learn more… | top users | synonyms

-1
votes
1answer
22 views

Divisibility test for 720

Use the divisibility test where possible to list all factors of 720 Please show further examples where appropriate, thank you.
1
vote
1answer
33 views

If $m | (8n +7)$, $m | (6n + 5)$, prove that $m = ± 1$

If $m | (8n + 7)$, $m | (6n + 5)$,prove that $m = ± 1$ -We have just starting going over the "divides" notation, and I am aware of a few properties and theorems from my notes. I am; although, a bit ...
5
votes
3answers
92 views

The only positive integers that divide successive numbers of the form $n^2+3$ are $1$ and $13$

I stuck with this problem, I don't know how to start with. Prove that the only positive integers that can divide successive numbers of the form $n^2+3$ are 1 or 13.
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
23 views

Divisibility: $60 \mid (2x-y)(2y-z)(3z+2x)$, if $8x-10y+27z=0$

As the title says, given $x,y,z \in \mathbb{Z}$, where $8x-10y+27z=0$, prove that $(2x-y)(2y-z)(3z+2x)$ is divisible by $60$. I tried to bring the formula in a format of $(\cdots)(8x-10y+27z) + ...
1
vote
3answers
38 views

Proof of divisibility: $17 \mid 3 \cdot 5^{2015} + 2^{2017} \cdot 5^{670}$ [on hold]

As the title says, prove that $3 \cdot 5^{2015} + 2^{2017} \cdot 5^{670}$ is divisible by $17$.
1
vote
2answers
64 views

Proof that $(2^m - 1, 2^n - 1) = 2^d - 1$ where $d = (m,n)$ [duplicate]

$(2^m - 1, 2^n - 1) = 2^d - 1$ where $d = (m,n)$ my work: I assumed $m = da$ , $n = db$ for $a,b \in \mathbb{Z}$. Now, $2^m - 1$ = $2^{da} - 1$ = $(2^d)^a - 1$ = $x^a - 1$ where $x = 2^d$. similarly ...
-1
votes
5answers
38 views

Divisibility by 101; a problem with induction [closed]

I was trying to show that $10^{2n}+(-1)^{n+1}$ is divisible by $101$. Would anyone help me with the induction step please?
13
votes
14answers
2k views

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

How can I prove that the following polynomial expression is divisible by 3 for all integers $k$? $$k^3 + 3k^2 + 2k$$
0
votes
1answer
22 views

Prove a relation is transitive

I've stumbled upon this question in my discrete math book: Prove $$ R = \{(x,y) \in N \times N \ | \ 2x \mid y^2 \} $$ is transitive. I tried thinking about it having to do something with division ...
0
votes
1answer
41 views

What is the simplest way to show that ${(p-1)! \over (k)!(p-k)!}$ is an integer?

In the proof of $p$ | $\binom{p}{k}$ (p divides $\binom{p}{k}$) where $p$ is prime, what is the simplest way to show that $${(p-1)! \over (k)!(p-k)!}$$ is an integer?
2
votes
2answers
50 views

Is this true :$\zeta(s-1)=\sum_{n=1}^{\infty}\frac{\gcd(n,n)}{{\operatorname{lcm}(n,n)}^{s}}$?

I would like to give other representation for zeta function using fundemental arithmitic I have got this: $\zeta(s-1)=\sum_{n=1}^{\infty}\frac{\gcd(n,n)}{{\operatorname{lcm}(n,n)}^{s}}$ where ...
0
votes
1answer
15 views

Number of positive integral divisors

I understand in order to find number of divisors, you need to follow following method, But I don't seem to find why it works. In order to find number of divisors a number has, you find the prime ...
4
votes
5answers
152 views

Looking for a non-combinatorial proof that $a! \cdot b! \mid (a+b)!$

(I use $a$ and $b$ to denote natural numbers.) Question. Without appealing to the combinatorial interpretation of $$\frac{(a+b)!}{a! b!}$$ as a multinomial coefficients, is there a proof that for ...
0
votes
2answers
69 views

The method of solving for a factor of $90!$ [duplicate]

If $90! = (90)(89)(88)...(2)(1)$, then what is the exponent of the highest power of $2$ which will divide $90!$ ? How would I apply one of the easiest method from Here? I need help on applying ...
0
votes
1answer
33 views

Divisibility criteria

Notice that by $\mod 7$ we have $$6!\equiv -1 (\mod 7)$$ $$5!1!\equiv 1 (\mod 7)$$ $$4!2!\equiv -1 (\mod 7)$$ $$3!3!\equiv 1 (\mod 7).$$ Calculate $10!, 9!1!, 8!2!, 7!3!, 6!4!, 5!5!$ by ...
1
vote
2answers
79 views

Using binomial theorem to prove $a | b^n \Rightarrow a | b$. ( | is divides, a prime, n integer > 1)

I tried expanding $(b-a+a)^n=$[$(b-a)+a$]$^n$ but it just seemed to further complicate the problem. I also tried to prove the contrapositive but that doesn't seem to lead to anywhere to. Is there any ...
7
votes
2answers
123 views

Prove that if $7^n-3^n$ is divisible by $n>1$, then $n$ must be even.

I tried using factorization of $a^n-b^n$ for odd $n$ in an attempt to work through to a situation where the factors are such that they cannot have n as a factor. But I reached nowhere. Here's how I ...
2
votes
8answers
140 views

is $7^{101} + 18^{101}$ divisible by $25$?

I am not able to find a solution for this question. I am thinking in the lines of taking out some common element like $(7\cdot 7^{100}) + (18\cdot18^{100})$ but couldn't go anywhere further.
7
votes
4answers
128 views

Find the remainder when ${{5^5}^5}^5$ is divided by $24$

Find the remainder when ${{5^5}^5}^5$ is divided by $24$ I tried using congruence modulo. $$5^2\equiv1\mod{24}$$ $$5^5=125\mod{24}$$ But this does not give the correct answer.
1
vote
4answers
68 views

Prove that for every natural $n$, $(n^2 + n)(n^2 + 2)$ can be divided by $6$

Prove that for every natural number $n$, $(n^2 + n)(n^2 + 2)$ can be divided by $6$. I've noticed that $(n^2 + n) = n(n+1)$ so these are two successive numbers hence one of them can be divided by ...
0
votes
1answer
452 views

Dividing the linear congruence equations

$$42x \equiv 12 \pmod {90}$$ This is a pretty simple congruence equation. $\gcd(42,90)=6$; $6|12 \implies $ a solutions exists. I've always been solving congruence equations with that scheme: ...
7
votes
2answers
285 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
0answers
22 views

How do i show this :$\lim_{k\to\infty} \frac{\sigma_{2k+1}(n)}{\sigma_{2k-1}(n)}=n²$ if it is true?

I run some computation in wolfram alpha I find for many fixed values of $n$ and for an arbitrary integer $k$ the ratio : $\frac{\sigma_{2k+1}(n)}{\sigma_{2k-1}(n)}$ close to $n²$ . My question here ...
2
votes
2answers
261 views

Show that if $ar + bs = 1$ for some $r$ and $s$ then $a$ and $b$ are relatively prime

We were given the following problem as an assignment, we proved the converse in class for prime numbers; however, we can't use the assumption that $\operatorname{gcd}(a,b) = 1$. So I am struggling to ...
0
votes
3answers
32 views

Divisibility of integer numbers

If we have two integers $a$ and $b$ such that $a = \frac{5b}{6}$, is $a$ divisible by $5$? If so, why is that? I don't see it.
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!)} ...
0
votes
0answers
39 views

Show that $504 \mid n^9 − n^3 $ for any integer $n$ [duplicate]

Not sure how to start this. I know that $504 =2 \times 2 \times2 \times 3 \times 3 \times 7$.
4
votes
0answers
60 views

What is the smallest prime factor of the number $14^{14^{14}}+13\ $?

What is the smallest prime factor of the number $$N\ :=\ 14^{14^{14}}+13\ ?$$ The number of digits of $N$ is $12,735,782,555,419,983$ (The number of digits of $N$ has itself $17$ digits). The first ...
7
votes
2answers
634 views

Prove that greatest common divisor of two numbers multiplied with itself divides the product of those numbers

$a, b, c \in \mathbb{N} $ if $c$ is the greatest common divisor of $a$ and $b$, $c^2$ divides $a\cdot b$. $c = \gcd(a, b) \implies c^2|ab $ How would I prove this? I understand why this sentence is ...
1
vote
1answer
12 views

When does:$(p^y+1 )\bmod (p^x+1)=0 $ if $(y,x)=1$ and $p $ is a prime number?

I'm interesting to look the solution of this equation :$$(p^y+1 )\bmod (p^x+1)=0 $$ at a least to see an example of the two coprime $y, x$ for which $(p^y+1 )\bmod (p^x+1)=0 $ but i don't succed , ...
0
votes
1answer
80 views

Any counter example for this claim?

I would like to proof or disproof this claim ,but i don't have enough information about divisor function structure . Claim : for any positive integer $x, y ,n $ such that :$x\neq y$ and ...
1
vote
3answers
89 views

Suppose $a \in \mathbb{Z}.$ Prove that $5 \mid 2^na$ implies $5 \mid a$ for any $n \in \mathbb{N}$

This question is supposed to be solved by induction, however I'm unsure of where to get my base case from exactly, because the question is asking about both $a$ and $n$. I started with my base case ...
5
votes
3answers
133 views

Is $x^2+x+1$ divisible by $101$, if $x\in\mathbb Z$?

Prove $x^2+x+1$ isn't divisible by $101$, for any $x\in\mathbb Z$? I think the way of solving the problem it by using "Fermat's Little Theorem".
3
votes
5answers
110 views

Prove $a/b+b/a$ for $a$ and $b$ natural is only natural for $a=b$ [closed]

Is it possible to prove that for any natural $a,b$ the value of $a/b+b/a$ will not be natural with exception $a=b$?
3
votes
2answers
158 views

Find all integer solutions to $a+b+c|ab+bc+ca|abc$

As you can see from the title, I am trying to find all integer solutions $(a,b,c)$ to $$(a+b+c) \ \lvert\ (ab+bc+ca) \ \lvert\ abc$$ (that is, $a+b+c$ divides $ab+bc+ca$, and $ab+bc+ca$ divides ...
2
votes
3answers
150 views

Prove that $3^x + 3^{x-2}$ ends with $0$ for any integer $x > 1$

I think that $3^x+3^{x-2}$ ends in a $0$ (i.e. is divisible by $10$) $\forall x \in \Bbb Z, x > 1$. Examples: $3^2+3^{2-2}=9+1=10 \\ 3^3+3^{3-2}=27+3=30 \\ 3^4+3^{4-2}=81+9=90 .$ In fact, I ...
4
votes
5answers
735 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 ...
26
votes
0answers
343 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 ...
27
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 ...
0
votes
1answer
29 views

Computation of bernuli number

Trying to follow the algorithm to calculate Bernulli number. On the page 4 it is written: $$d = \prod_{p-1|m}p$$ which in my opinion means that I have to find all the numbers $p-1$ that divide $m$ ...
-4
votes
0answers
25 views

Numbers with 12 divisors

Find the positive integers $n$ with exactly $12$ divisors $1 = d_1 < d_2 < ... < d_{12} = n$ such that the divisor with index $d_4(ie, d_{d_4} - 1)$ is $(d_1 + d_2+ d_4)d_8$.
0
votes
2answers
48 views

Prove $n!\mid\prod_{k=i}^{i+n-1}k$

I have no idea how to prove this, I haven't yet learned much about this kind of product. $$ n!\mid\prod_{k=i}^{i+n-1}k $$
3
votes
2answers
126 views

Proving $r!$ divides the product of r succesive positive integers

I have to prove the following theorem: Prove that the product of $r$ consecutive positive integers in divisible by $r!$ I am having a hard time getting a generalization down for the full set of ...
-1
votes
6answers
73 views

Proving $2^{2n}-1$ is divisible by $3$ for $n\ge 1$

So I decided to use induction. First, I started with my base case, $P(1) = 2^{2(1)}-1=3,$ so it's true. That means if $n = k$ is true, then $n = k+1$ is true also. So, $P(n+1)-P(n)$ would also be ...
4
votes
2answers
52 views

Prove that $2^n+(-1)^{n+1}$ is divisible by 3.

Prove that $2^n+(-1)^{n+1}$ is divisible by 3 for $n\in\mathbb{N}$. My attempt: For $n=1$: $2^1+(-1)^2 = 2 + 1 = 3, 3 |3$ We assume that $3|(2^n+(-1)^{n+1})$ Then for $n+1$: $2^{n+1} + ...
1
vote
0answers
23 views

Recursive division by Burnikel and Ziegler, explaining the breaking down of large numbers

I am looking at Fast Recursive Division by Burnikel and Ziegler. I understand $DivTwoDigitsByOne( ... )$ and $DivThreeHalvesByTwo( ... )$ as they break the numbers down. So, for example, ...
2
votes
2answers
85 views

How to prove that $(p-1)^2$ $\mid$ $(p-1)!$ when $p$ is a prime number and $p>5$?

I say that $p-1$ $\mid$ $(p-1)!$ then I want to prove that $p-1$ $\mid$ $(p-2)!$. I started by saying that $p-1$ is an even number so $2\mid (p-1)$ and that means that $\frac{p-1}{2}$ is an integer. ...
0
votes
1answer
19 views

How to prove divisibility implication.

If 11|(12i+3j) and 22|j then 11|i. This is the implication. Focusing on 22|j. If J is divisible by 22 that means its an even number and is also divisible by 11. Can I go from 22|j to 11|(j/2)? I ...