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

learn more… | top users | synonyms

2
votes
1answer
18 views

How to work out the greatest lower divisor in a pair of divisors?

I don't know what it's called, so it's hard to explain, but say we have the number $12$, which can be $1 \times 12$, $2 \times 6$, or $3 \times 4$. I want the $[3, 4]$ pair because $3$ is the ...
3
votes
3answers
66 views

Compute a natural number $n\geq 2$ s.t. $p\mid n \Longrightarrow p^2\nmid n$ AND $p-1\mid n \Longleftrightarrow p\mid n$ for all prime divisor p of n.

Question: Compute a natural number $n\geq 2$ that satisfies: For each prime divisor $p$ of $n$, $p^2$ does not divide $n$. For each prime number $p$, $p-1$ divides $n$ if and only if $p$ divides ...
7
votes
4answers
207 views

What is the sum of all the natural numbers between $500$ and $1000$.

What is the sum of all the natural numbers between $500$ and $1000$ (extremes included) that are multiples of $2$ but not of $7$?
0
votes
1answer
39 views

If $\gcd(a,b)=D$, then why must there exists integers $x$ and $y$ such that $ax+by=D$? [closed]

If the greatest common divisor of two integers $a,b$ is $D$, then why must there exists two integers $x,y$ such that $ax+by=D$?
1
vote
2answers
48 views

Number of ways of selecting 3 numbers from $\{1,2,3,\cdots,3n\}$ such that the sum is divisible by 3

Find the Number of ways of selecting 3 numbers from $\{1,2,3,\cdots,3n\}$ such that the sum is divisible by 3. (Numbers are selected without replacement). I made a list like this: The sum of ...
2
votes
1answer
64 views

Find all $n$ such that $3^{2n+1}-4^{n+1}+6^n$ is prime

I'll try to format my question in a manner such that you can skip (irrelevant) parts. Exercise: Find all natural $n$ such that $3^{2n+1}-4^{n+1}+6^n$ is prime. Motivation: I'm trying to ...
4
votes
4answers
183 views

Remainder when ${45^{17}}^{17}$ is divided by 204

Find the remainder when ${45^{17^{17}}}$ is divided by 204 I tried using congruence modulo. But I am not able to express it in the form of $a\equiv b\pmod{204}$. $204=2^2\cdot 3\cdot 17$
1
vote
1answer
52 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 ...
1
vote
3answers
44 views

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

As the title says, prove that $3 \cdot 5^{2015} + 2^{2017} \cdot 5^{670}$ is divisible by $17$.
2
votes
2answers
25 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) + ...
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$$
0
votes
1answer
30 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
46 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?
1
vote
2answers
62 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
311 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 ...
0
votes
2answers
76 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 ...
5
votes
5answers
176 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 ...
1
vote
2answers
107 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 ...
0
votes
1answer
34 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 ...
5
votes
3answers
103 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.
7
votes
4answers
139 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
71 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 ...
1
vote
0answers
23 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 ...
0
votes
3answers
48 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.
0
votes
0answers
43 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
69 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 ...
1
vote
1answer
15 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
81 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
109 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
142 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
115 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$?
7
votes
2answers
655 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 ...
2
votes
3answers
162 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 ...
0
votes
3answers
95 views

Proof that $(3\cdot 2^n-1)$ is not a multiple of $17$ for any value of $n$ [closed]

Prove that $3\cdot 2^n-1$ is not a multiple of $17$ for any positive integer $n$.
0
votes
1answer
30 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$ ...
1
vote
0answers
37 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, ...
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 ...
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 ...
1
vote
2answers
54 views

Proof: divisibility

Question: For all $a, b, c \in \mathbb{Z}$, if $a\mid bc$, then $a\mid b$ or $a\mid c$. Is this true? My answer: True. (Proof by contrapositive) Proof that if $a \nmid b$ and $a \nmid c$, then $a ...
0
votes
1answer
28 views

find smallest number $M$ for which the remainder of $N/M$ is equal to $3$

given a positive integer $N$ greater than $3$, is there a smart or algorithmic way to find the smallest number $M$ for which the remainder of $N/M$ equals $3$? one obvious answer is always $N-3$, but ...
4
votes
2answers
169 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 ...
1
vote
2answers
26 views

Prove: If $a|c \wedge b | c \wedge (a, b) = d \Rightarrow ab | cd$

I know that $(a,b)=d \Rightarrow ma+bn=d, (m,n\in Z)$. $ma+bn=d/*c \Rightarrow cma+cnb=cd$ And I'm kinda stuck here. Any help or hint is appreciated.
2
votes
1answer
42 views

Simple equation - prove division

this should be simple. I am helping my son with one assignment but I simply cannot solve it. I really exhausted ideas. The problem is: prove that $\displaystyle {(m^2 + 5m)(m^2 + 5m + 10) + 24}$ can ...
-5
votes
3answers
66 views

Are there a closed form of near solutions to the equation: $2\sigma(n)=3n$? [closed]

I would like to check the solution of this equation: $$2\sigma(n)=3n$$ where $\sigma(n)$ is the sum divisor function. Note: I know only $n=2$ is a theortitical solution, are there a closed form of ...
2
votes
4answers
65 views

Induction: Prove that $5^{3n} + 7^{2n-1}$ is divisible by $4$

Prove that $5^{3n} + 7^{2n-1}$ is divisible by $4$ for all $n \in \mathbb{N}$. For $n=1$, $\Rightarrow 5^3 + 7^1 \Rightarrow 132 \mid 4$ (which is divisible by $4$) Let us assume given equation ...
1
vote
2answers
33 views

Suppose $d$ is a common divisor of two numbers $a_0$ and $a_1$, can $d$ be written as a linear combination of $a_0$,$a_1$ with integer coefficients?

Suppose $d$ is a common divisor of two numbers $a_0$ and $a_1$, can $d$ be written as a linear combination of $a_0$,$a_1$ with integer coefficients? i.e. there exists two integers $i_0,i_1 \in \Bbb Z$ ...
0
votes
1answer
17 views

Can the min/max value of a quotient be calculated for a simple division?

If I have a simple division $x \over y$ I can rewrite it as $x = Qy +R$, (where Q is the Quotient and R is the remainder). I know that $|y| > R \ge 0$. Is there a similar rule for the quotient?
1
vote
2answers
31 views

Divisibility (algebra, number theory).

Suppose you have $$a b c = m$$ $$a|y$$ $$b|y$$ $$c|y$$ Does that imply that $$m|y$$ $$am_1 = y$$ $$bm_2 = y$$ $$cm_3 = y$$ $$mm_1 m_2 m_3 = y^3$$ ??
5
votes
4answers
85 views

If the $81$ digit number $111\cdots 1$ is divided by $729$, the remainder is?

If the $81$ digit number $111\cdots 1$ is divided by $729$, the remainder is? $729=9^3$ For any number to be divisible by $9$, the sum of the digits have to be divisible by $9$. The given number ...
4
votes
4answers
57 views

If $a\mid b^2, b^2\mid a^3,\ldots ,a^n\mid b^{n+1},b^{n+1}\mid a^{n+2},\ldots$ then $a=b$ [duplicate]

I'm stuck with this problem : Let $a,b$ positive integers such that $$a\mid b^2, b^2\mid a^3,\ldots ,a^n\mid b^{n+1},b^{n+1}\mid a^{n+2},\ldots$$ Show that $a=b$. If were $ b > a $ then $\lim_{n ...