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

learn more… | top users | synonyms

0
votes
2answers
11 views

$a =\prod_{i = 1}^{r} p_{i}^{a_i}$ with $a_{i} > 0$ for each $i$ is the canonical representation of $a$…

$a =\prod_{i = 1}^{r} p_{i}^{a_i}$ with $a_{i} > 0$ for each $i$ is the canonical representation of $a$,Prove that $a$ is the square of an integer if and only if $a_i$ is even for each $i$. -The ...
0
votes
1answer
14 views

$a =\prod_{i = 1}^{r} p_{i}^{ai}$ with $a_{i} > 0$ for each $i$ is the canonical representation of $a$…

$a =\prod_{i = 1}^{r} p_{i}^{ai}$ with $a_{i} > 0$ for each $i$ is the canonical representation of $a$, deduce a formula for the sum of the squares of the positive divisors of $a$. -The section we ...
3
votes
3answers
48 views

Show that we cannot have a prime triplet of the form $p$, $p + 2$, $p + 4$ for $p >3$

Show that we cannot have a prime triplet of the form $p$, $p + 2$, $p + 4$ for $p >3$ I was a bit lost with this proof until I found a similar looking proof-based question from a previous ...
-1
votes
0answers
20 views

$k$ be a positive integer ; $\{a_n\}$ be a sequence of positive integers such that $\gcd(m,n)=1 \implies a_m^k+a_n^k|m^k+n^k$ ; then $a_n=n$?

Let $k$ be a positive integer ; $\{a_n\}$ be a sequence of positive integers such that g.c.d.$(m,n)=1 \implies a_m^k+a_n^k|m^k+n^k$ ; then is it true that $a_n=n , \forall n \in \mathbb N$ ?
1
vote
1answer
67 views

Prove or reject: if $a^2|b^3$ then $a|b$

I tried to find a counter example but failed!! If $a^2|b^3$ then it is obvious that $a|b^3$ because $b^3=ka^2=(ka)a=k'a$ but we hardly can say $a|b$
1
vote
1answer
99 views

Determine all $k$ such that $k^3+k+1$ is divisible by 11

The task is the following: Determine all $\ k\in\mathbb Z$ such that $k^3+k+1$ is divisible by 11 I assumed that "$k^3+k+1$ is divisible by 11" is saying $11|k^3+k+1$. That means I can rewrite it as ...
2
votes
1answer
17 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
63 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
3answers
98 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
36 views

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

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
34 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 ...
1
vote
1answer
48 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 ...
3
votes
4answers
116 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$
0
votes
1answer
40 views

Divisibility test for 720 [closed]

Use the divisibility test where possible to list all factors of 720 Please show further examples where appropriate, thank you.
1
vote
1answer
46 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
41 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
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) + ...
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$$
0
votes
1answer
24 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
42 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
54 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
28 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
72 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 ...
4
votes
5answers
159 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
85 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
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 ...
5
votes
3answers
98 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
133 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 ...
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
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.
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
62 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
14 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
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
135 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
112 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
636 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
151 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
90 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$.
-4
votes
0answers
26 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
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$ ...
1
vote
0answers
24 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 ...
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 ...
1
vote
2answers
52 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
27 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 ...
3
votes
2answers
161 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
24 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.