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)

6
votes
1answer
48 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
28 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
37 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
17 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 ...
1
vote
2answers
3k views

If $\gcd(a,b)=1$ and $a$ and $b$ divide $c$, then so does $ab$

Using divisibility theorems, prove that if $\gcd(a,b)=1$ and $a|c$ and $b|c$, then $ab|c$. This is pretty clear by UPF, but I'm having some trouble proving it using divisibility theorems. I was ...
2
votes
1answer
22 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
57 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
63 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
34 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
49 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 ...
1
vote
5answers
62 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
42 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 ...
0
votes
2answers
36 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
64 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.$$
8
votes
1answer
426 views

$f'/f\in\mathbb{Z}[[x]]$ for polynomials vs. formal power series $f$

I am curious about the following problem from MIT's Problem Solving Seminar (#26 here, though the link may stop working after a few weeks): Let $f(x) = a_0+a_1x+\cdots\in\mathbb{Z}[[x]]$ be a ...
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$$ ...
2
votes
3answers
158 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 ...
0
votes
1answer
25 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)$.
1
vote
1answer
23 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?
-2
votes
1answer
21 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
39 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$ ...
0
votes
3answers
23 views

Let $a$ be a positive integer. The sum of $a$ consecutive integers is divisible by $a$ if and only if $a$ is odd.

How would one prove this? Other than using cases to prove the if and only if part, how would I prove each case to complete the proof?
0
votes
3answers
109 views

How to prove if $n$ is prime and $n | a^2$ then $n | a$?

My professor assigned this for homework but I don't understand how to connect the dots. He suggested using the fact that $\gcd (x,y) \cdot \operatorname{lcm} (x,y) = xy$ but I'm not sure how that's ...
2
votes
2answers
35 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
47 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
2answers
50 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 ...
1
vote
0answers
51 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
3answers
45 views

Using long division on polynomials

Can anyone show me how to find $x^5 + 1$ divided by $x^3 + 1$?
1
vote
1answer
40 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 ...
0
votes
1answer
19 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 ...
0
votes
1answer
38 views

Remainder of trick-number divided by 9

How can I calculate the remainder of something like $199\cdot 741934^{1234}$ by 9?
14
votes
7answers
656 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 ...
0
votes
2answers
89 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 ...
6
votes
3answers
82 views

Show that $9\mid a^2$ if given that $6\mid a$

Does this prove I made seem correct to show that if $6$ divides $a$ then $9$ divides $a^2$ If $6\mid a$, then $a = 6k$ (k is some integer). Then $a^2 = 36k^2 = 9(4k^2)$. Which means that $9\mid ...
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 ...
4
votes
1answer
129 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} - ...
0
votes
0answers
54 views

Finding an asymptotic formula for $f(m,n)=\sum_{\substack{d\mid m \\ d\leq n}}1$?

$$f(m,n)=\sum_{\substack{d\mid m \\ d\leq n}}1$$ Here $n<m$ and $m$, $n$ are positive integers.
2
votes
2answers
115 views

Greatest common divisor with one parameter and condition

I have this homework question: Find $d = \gcd(10x+6, 3x+1) $ where $d > 5$ and $x$ is natural How can I solve it?
2
votes
4answers
80 views

Prove: If $\gcd(a,b) = 1$ and $c|a$ and $d|b$, then $\gcd(c,d)=1$

I've a problem proving the following: If $\gcd(a,b) = 1$ and $c|a$ and $d|b$, then $\gcd(c,d)=1$ I've tried to set $a = c\cdot p$ and $b = d\cdot q$. But then I'm stuck proofing it formally.
0
votes
1answer
82 views

Why does the number of divisors of a superior highly composite number is always a highly composite number up to 720720 ? (the only exception is 120)

I've calculated the number of divisors of every superior highly composite number up to $10^{27}$: http://oi59.tinypic.com/ndaijo.jpg The number of divisors of a superior highly composite number is ...
-1
votes
3answers
112 views

Prove that if $n+1$ is divisible by $m$ then $n^2-1$ is also divisible by $m$. [closed]

Prove that if $n+1$ is divisible by $m$ then $n^2-1$ is also divisible by $m$. And prove that if $n^2-1$ is divisible by $m$ then $n+1$ is also divisible by $m$.
0
votes
1answer
77 views

Have you seen this theorem before? (GCD divides, neccessary & sufficient condition)

Conjecture. Let $a,b, c\in \Bbb{Z}, b \neq 0$, The following conditions are equivalent: (1) $d = \gcd(a,b)$ divides c. (2) There's a polynomial in $f \in \Bbb{Z}[X,Y]$ with $c$ constant term, such ...
2
votes
3answers
96 views

Is it true that $5^k \mid f(5^k)$?

I guess if it is true that $5^k \mid f(5^k)$, where $f(n)$ denotes the $n$-th Fibonacci's number. I have tried to prove it by induction on $k$, but nothing. Have you got any ideas?
1
vote
1answer
28 views

Complex matrix division when only the amplitude of the vector to be divided is known.

Let A be a known complex matrix, B a complex vector, and C the complex vector to be solved. Imagine that we know that AC = B . Let assume that the number of lines of A and B are as many as needed. (In ...
2
votes
3answers
79 views

If $3$ divides $q^3$, is it true that $3$ divides $q$?

I think this is true because of prime factorisations, i.e. If $3$ a factor of the prime factorisation of $q^3$, then $3$ is a factor of the prime factorisation of $q$. Therefore If $3$ divides ...
1
vote
4answers
57 views

Help with groups

let $G$ be a finite group with $e$ Identity element and let $a$ and $b$ belong to $g$ prove that if: $\gcd(o(a),o(b)) =1$ then $\langle a \rangle \cap \langle b \rangle = \{ e \}$. if someone can ...
2
votes
1answer
50 views

Prove $\gcd(k, l) = d \Rightarrow \gcd(2^k - 1, 2^l - 1) = 2^d - 1$ [duplicate]

This is a problem for a graduate level discrete math class that I'm hoping to take next year (as a senior undergrad). The problem is as stated in the title: Given that $\gcd(k, l) = d$, prove that ...
2
votes
1answer
65 views

How do I work out the aspect ratio from the resolution by hand?

For $1024 \times 768$ I can see that $768/1024 = 0.75$, i.e. $\frac34$, so $4:3$ makes sense. How do I do it for other resolutions like $1920 \times 1080$ though?
1
vote
1answer
42 views

Is my proof right for this divisibility proof?

Prove For all integers $x$ if for all natural numbers $y$, $x$ does not divide $y$, then $x = 0$. I start by saying that $x\neq 0$ then $x\mid y$ there is exists an integer $d$ such that $xd=y$ if ...