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)

-1
votes
4answers
46 views

How many divisors are there in 2015, that is d(2015)? [on hold]

This is the question raised in our class to check our understanding in divides.
1
vote
1answer
40 views

Question in elementary number theory

I have a question. Suppose that $a$ and $b$ are two natural numbers so that $ a<b$ and $ a\nmid b$. Put $ d=ka$, where $ k\not=0,1,t\dfrac{b}{\gcd(a,b)}$, for $ t\geq 1$. I want to prove that $ ...
0
votes
5answers
40 views

How do you prove this divisibility?

If $n$ is any natural number, prove that $3\mid 2^{2^n}-1$ is true. I can't find out how to do it. Thanks.
1
vote
1answer
45 views

Characterizing the primes which don't divide any Pell-Lucas number(s)

For integer $n$, let $P_n$ be a Pell number, and $Q_n$ its companion. Is there a characterization of the prime numbers $p$ which don't divide any $Q_n$? By brute-force search, I found that this ...
3
votes
1answer
63 views

Probability that two random integers have only one prime factor in common

The probability that two integers picked at random are relatively prime is known to be $1/\zeta{(2)}=6/\pi^2\approx0.607927...$. Generalizing, the probability that $n$ random integers have $\gcd=1$ is ...
0
votes
3answers
27 views

Help with understanding definition of divisibility in this case.

I have a proof that shows that if $5 \mid xy$ then $5 \mid x$ or $5 \mid y$. It's pretty clear to me that I can just say that suppose $5 \mid x$, then $x=5a$, where $a$ is an integer. then $xy = ...
3
votes
5answers
563 views

The sum of three consecutive cubes numbers produces 9 multiple

I want to prove that $n^3 + (n+1)^3 + (n+2)^3$ is always a $9$ multiple I used induction by the way. I reach this equation: $(n+1)^3 + (n+2)^3 + (n+3)^3$ But is a lot of time to calculate each ...
1
vote
0answers
24 views

Find the Conditions

Let $a, b, c, d, r, s \in \mathbb{N}$. Find the necessary and sufficient conditions under which $r \mid (a-b)$ and $s \mid (c-d)$ $\implies $\operatorname{lcm}(r,s)\mid(ac-bd)$. A little thought ...
0
votes
1answer
31 views

How to get all divisors of an integer using only pen & paper

Is there any fast approach to get all divisors of an integer by only using pen & paper?
0
votes
0answers
62 views

Counting maximum moves

Given two arrays, each of size N denoted by A1,A2...AN and B1,B2...BN. Let us maintain two sets S1 and S2 which are empty initially. In one move ,Pick a pair of indexes (i, j) such that : ...
2
votes
2answers
60 views

How to divide a number by $2$ numbers?

I have to distribute newspapers, and the printing company gives it to me in bundles of $15$ and $25$, now if a store wants $115$ I will have to send them $4 \times 25$ and $1 \times 15$, or if they ...
0
votes
2answers
348 views

Finding Coprime triplets

Given a sequence a1, a2, ..., aN. Count the number of triples (i, j, k) such that 1 ≤ i < j < k ≤ N and GCD(ai, aj, ak) = 1. Here GCD stands for the Greatest Common Divisor. Example : Let N=4 ...
0
votes
1answer
42 views

Polynomials - getting wrong answer using Euclidean algorithm

I am finding the GCD of $a = x^3 + 11/3x^2 + 17/4x + 3/2$ and $b = 3x^2 + 22/3x + 17/4$ using the Euclidean algorithm. So I divide $a/b$ and get $q$ and $r$ such that $a = qb + r$. Then, according to ...
0
votes
1answer
21 views

Position of switches based on divisibility

There is a set of $1000$ switches. Each has four different positions, called $A$, $B$, $C$, and $D$. When the position of any switch changes, it is only from $A$ to $B$, from $B$ to $C$, from $C$ to ...
0
votes
2answers
62 views

Find all values of for which the ratio is an integer

Find all values of $n$ for which, $$\dfrac{(\dfrac{n+3}{2}) \cdots n}{(\dfrac{n-1}{2})!}$$ is an integer. I have tried the problem for some primes. Each time it seemed true. But I still ...
6
votes
1answer
46 views

Sequences where each number is a divisor of one less than the next

Let $N,k$ be fixed. Call a sequence of positive integers $a_1,a_2,\dots,a_k$ good if for each $i$, $a_i$ is a divisor of $a_{i-1}-1$. Consider the set $$S = \{a_i : a_1,\dots,a_k \text{ is a good ...
2
votes
1answer
26 views

Group divisibility question

I have the following question which I can't make sense of, here is the entire question: If $G$ is a group, $b\in G, o(b)=k$ and $b^n = e$, show that $k|n$ What is $o(b)$? Please help.
1
vote
2answers
31 views

GCD question involving coprimes

How can I prove that if $\gcd(a, b) = 1$, then $\gcd(ab, c) = \gcd(a, c) \times \gcd(b, c)$? By eea there exists $ax+by=1$ from $\gcd(a,b)=1$ so a and be are co-primes there also exists $dk=a$ and ...
0
votes
1answer
16 views

Proving $k$ is a common divisor of $a$ and $b$ iff $k\,|\gcd(a,b)$ — converse

I'm currently trying to solve the converse of this statement is true after proving the normal version is true. If $k$ is a common divisor of $a$ and $b$, then $k \,| \gcd(a, b)$ So far I know the ...
2
votes
1answer
17 views

Questions relating to gcd

Assume a, b and c are positive integers. 1) Suppose that a | b. Show that gcd(a, c) ≤ gcd(b, c). 2) Suppose that a ≤ b. Is it necessarily true that gcd(a, c) ≤ gcd(b, c)? I'm having trouble with ...
0
votes
1answer
56 views

The binomial coefficients $\binom{n}{ p}$ are divisible by a prime $p$ only if $n$ is a power of $p.$

I'm looking for a "high school / undergraduate" demonstration for the: All the binomial coefficients $\binom{n}{i}=\frac{n!}{i!\cdot (n-i)!}$ for all i, $0\lt i \lt n$, are divisible by a prime $p$ ...
3
votes
1answer
60 views

If $k$ is an odd number then $3k^2 +16$ is not a perfect cube

I am pretty sure that the title is true. Could anybody please prove it? I am particularly interested in a proof that mostrly relies on divisibility.
0
votes
1answer
31 views

Finding greatest common divisor between two polynomials.

I have the following past exam question: Calculate $\operatorname{gcd}(x^3 + 2x^2 + 2,2x^2 + 1)$ in $\mathbb{F}_3$ Now I haven't encountered this sort of gcd before(usually I am trying to solve ...
1
vote
3answers
39 views

Prove that $(k.n)!$ is divisible by $(k!)^n$

Suppose $k,n$ are integers $\ge1$. Show that $(k.n)!$ is divisible by $(k!)^n$ I have simplified the problem and now, I need to prove that any $k$ consecutive integers is divisible by $k!$. However I ...
8
votes
6answers
730 views

Better Divisibility by 8

Everywhere I look, when you want to see if something is divisible by $8$ then you see if the last $3$ digits are divisible by eight. But how do you know if the last $3$ digits are divisible by $8$? ...
1
vote
5answers
58 views

$n \in \mathbb{N} \ 5|\ 2^{2n+1}+3^{2n+1}$

show for all $n \in \mathbb{N}$, $$5|\ 2^{2n+1}+3^{2n+1}$$ Indeed, we've to show that : $2^{2n+1}+3^{2n+1}=0[5] $ note that $2^{2n+1}+3^{2n+1}=2.4^n+3.9^n= $
1
vote
1answer
41 views

Prove that $f(n,p)$ is a non-square integer

Let, $$f(n,p)=(n+1)(n+2) \cdots (n+p-1)$$ Then show that $f(n,p)$ is a not a perfect square for all $n \in \mathbb{N}$ and for all odd primes $p$. Consider only the cases when ...
2
votes
5answers
61 views

Proof regarding divisibility

if $n\in\mathbb{Z}$, then $4$ does not divide $(n^2 - 3)$ I'm not sure how to approach this question, I know how to do questions that involve proving that it does divide but I'm unsure of how to do ...
1
vote
2answers
30 views

Contrapositive proof using rule of divisibility

Suppose $x,y,z$ are integers and $x \neq 0 $ if $x$ does not divide $yz$ then $x$ does not divide $y$ and $x$ does not divide $z$. So far I have: Suppose it is false that $x$ does not divide $y$ and ...
0
votes
2answers
59 views

Prove or disprove this implication

Prove or disprove: If $x, a, b > 0$ are integers such that $$\gcd(x-a, x+b) = 1\ \ \mbox{and}\ \ \gcd(2x-a, x+b) > 1,$$ then $$a+b = x.$$
2
votes
1answer
44 views

$[n,n+1]=\text{ ??????}$

I know the answer is $n(n+1)$, but I'm having trouble formulating an argument. I know by the definition, if I let $h=[n,n+1]$ $$h=nk_1, h=(n+1)k_2$$ $$nk_1=(n+1)k_2$$ ...
0
votes
1answer
24 views

Prove superpolynomial growth rate [duplicate]

Let $p(n)$ be the number of partitions of $n$. Prove that growth rate of $p(n)$ is superpolynomial, meaning that for every given $k$ there is $p(n)= \omega (n^k)$.
0
votes
0answers
2 views

Show that the HNF of the column vector $[a_{1},…,a_{n}]^{T}$ is exactly $[gcd(a_{1},…,a_{n}),0,…,0]^{T}$

HNF = Hermite Normal Form. I see why this is true by computing an example...and I know I need to use the Euclidean Algorithm...
1
vote
1answer
20 views

Find highest power of 2 that divides $3^{2^k}-1$

I am trying to find highest power of 2 that divides $3^{2^k}-1$ but I have no idea where to start - could you give me any hint?
1
vote
2answers
74 views

Divisibility problem!

Show that for any natural number n, between $n^2$ and $(n+1)^2$ one can find three distinct natural numbers $a,b,c$ such that $a^2+b^2$ is divisible by $c$. A friend and I found a general case that ...
-1
votes
1answer
16 views

Modified division, hyperreal numbers and transfinite derivatives

Suppose we are shooting from a cannon and measuring the speed of the projectile. The shorter period of time it takes for the projectile to reach the target, the faster it is. If the projectile hits ...
0
votes
1answer
34 views

What are the smallest numbers $n$ such that $\dfrac{d(n)}{\ln(n)} \geq k$ where $d(n) = \sigma_0(n)$ is the number-of-divisors function?

I have calculated $\dfrac{d(n)}{\ln(n)}$ on a few highly composite numbers up to 5040. Here is what I got: $\dfrac{d(120)}{\ln(120)} = 3.3420423$ $\dfrac{d(360)}{\ln(360)} = 4.0773999$ ...
2
votes
2answers
29 views

highest power of prime $p$ dividing $\binom{m+n}{n}$

How to prove the theorem stated here. Theorem. (Kummer, 1854) The highest power of $p$ that divides the binomial coefficient $\binom{m+n}{n}$ is equal to the number of "carries" when adding $m$ ...
1
vote
3answers
46 views

If there is an $a\in\mathbb{Z}$ with $a^{n-1}\equiv 1\mod n$ but $a^{\frac{n-1}p}\not\equiv 1$ for all primes $p\mid n-1$, then $n$ is a prime

Let $n\in\mathbb{N}$ with $n\ge 3$ and $a\in\mathbb{Z}$ such that $$a^{n-1}\equiv1\text{ mod } n\;\;\;\wedge\;\;\;a^{\frac{n-1}{p}}\not\equiv1\text{ mod }n\;\;\;\forall p\in\mathbb{P}:p\mid n-1$$ ...
1
vote
0answers
49 views

Showing DO NOT exist GCD of $6$ and $2+2 \sqrt{-5}$ in $\Bbb Z[\sqrt{-5}]$.

Showing DO NOT exist gcd of $6$ and $2+2 \sqrt{-5}$ in $\Bbb Z[\sqrt{-5}]$. I tried it. Suppose $d$ is GCD of $6$ and $2+2 \sqrt(-5)$. then there exist $x,y \in \Bbb ...
0
votes
1answer
17 views

$B$-powersmooth number divides $\mathrm{lcm}(1,2,3,\ldots B)$

Let $M$ be $B$-powersmooth (ie. all prime powers in $M$'s factorization are $\le B$). I want to prove that $M \mid \mathrm{lcm}(1,2,3,\ldots, B)$. I thought it would be easy to prove this using ...
-2
votes
0answers
38 views

GCD of two polynomials

Here is a question about polynomial division, does $\gcd(p(x), x^ (2m))$, where $m$ is max length of $p(x)$ (-edit here -) p(x) is a polynomial over a finite field (m is its length) equal the minimum ...
0
votes
1answer
27 views

Remainder of trick-number divided by 9

How can I calculate the remainder of something like $199\cdot 741934^{1234}$ by 9?
1
vote
1answer
39 views

$nc_i\mid\prod_{i=1}^3(nc_i+1)-1$ iff $\exists c\in 6\mathbb{N}:c_i=ic$

Let $c_1<c_2<c_3$ be natural numbers and $$C_n=\prod_{i=1}^3(nc_i+1)-1\;\;\;\;\;(n\in\mathbb{N})$$ I want to show that it holds $$\forall n\forall i : nc_i\mid ...
1
vote
2answers
43 views

Question about kth root of a reduced ring element.

Let $n > 1$ be a positive integer. Let $k > 1$ be a positive integer. Define the reduced polynomial rings $f_n = \Bbb R[X_n]/(1+(X_n)^{n})$ How do we know if $(X_n)^{1/k}$ is an element of ...
0
votes
2answers
69 views

Prove that if $n^2 - 1$ is divisible by a prime number $p$ such that $n - 1$ is not divisible by $p$, then $n + 1$ is also divisible by $p$.

If this proposition is false, please give at least $3$ counter-examples, and try to modify the proposition so that it becomes true. If the proposition is true, please try to prove this even more ...
0
votes
0answers
40 views

divisibility question involving primes

I have a question concerning the following divisibility problem. For any prime $p$ we define set: $\mathtt{V_{p}}:=\Biggl\{F\in\Phi\Biggl|\begin{cases}p^2\nmid ...
0
votes
1answer
14 views

Show that if $a=bq+r $ and $d|a$ and $d |b $, then $d|a-bq $

Show that if $a=bq+r $ and $d|a$ and $d |b $, then $d|a-bq $ That is show that if $d $ divides $a $ and $a=bq+r $ then $d $ divides $a-bq $. Here $d |a $ means "d divides a", that is $ a=dk $ where ...
2
votes
3answers
155 views

Find positive integers $(x,n)$ such that $x^{n} + 2^{n} + 1$ is a divisor of $x^{n+1} +2^{n+1} +1$

Find all positive integers $(x,n)$ such that $x^{n} + 2^{n} + 1$ is a divisor of $x^{n+1} +2^{n+1} +1$ I encountered this question in one of my monthly assignments. Unfortunately, I don't know ...
4
votes
1answer
117 views

$\sum\limits_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}$ isn't divisible by 5

I have no idea Prove that for any $n$ natural number this sum $$\sum\limits_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}$$ isn't divisible by $5$. $\begin{array}{l} \left( {1 + x} \right)^{2n + 1} - ...