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)

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)$.
1
vote
1answer
21 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
79 views

Solving $a^2+b^2\equiv 0$ mod $c$ for distinct integers $a,b,c$ constrained between two consecutive squares

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
17 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
38 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
30 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
0answers
50 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
18 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
29 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
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 ...
1
vote
2answers
45 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
76 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
156 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
118 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
113 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?
0
votes
1answer
72 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
vote
1answer
127 views

Why isn't $1$ a superior highly composite number?

A superior highly composite number is a positive integer $n$ for which there is an $\epsilon>0$ such that $\dfrac{d(n)}{n^\epsilon} \geq \dfrac{d(k)}{k^\epsilon}$ for all $k>1$, where the ...
0
votes
1answer
76 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 ...
-1
votes
3answers
111 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$.
2
votes
3answers
95 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 ...
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
3answers
78 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 ...
2
votes
1answer
44 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 ...
0
votes
0answers
31 views

Let $f(x)\in K[x]$ ($K$ field). Prove that if $(f(x),f´(x))=1$ (greatest common divisor is 1) then $f(x)$ does not have multiple roots in $K$

Please I would like you to tell me if my proof is correct Let $f(x)\in K[x]$ ($K$ field). Prove that if $(f(x),f´(x))=1$ (greates common divisor is 1) then $f(x)$ does not have multiple roots in $K$ ...
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 ...
2
votes
1answer
63 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
2answers
66 views

Proving a Pellian connection in the divisibility condition $(a^2+b^2+1) \mid 2(2ab+1)$

I'm trying to prove that all integer solutions $a > b \ge 0$ to the divisibility condition in the title, namely $$(a^2+b^2+1) \mid 2(2ab+1),$$ are given by ...
1
vote
0answers
14 views

Efficient way needed

Given N, M find the : GCD(1, 1) * GCD(1, 2) * … * GCD(1, M) * GCD(2, 1) * GCD(2, 2) * … * GCD(2, M) * … * GCD(N, 1) * GCD(N, 2) * … * GCD(N, M) modulo 10^9+7 Constraints: 1 <= N, M <= 2 * ...
1
vote
1answer
39 views

How to prove $D(n)<2n(\log\log n)$?

How to prove $D(n)<2n(\log\log{n})$ for all sufficiently large $n$ where $D(n)$ is the Divisor summatory function.
2
votes
1answer
68 views

Prove that a sequence of $11$ numbers always contains six numbers summing up to a multiple of $6$.

Prove that a sequence of $11$ numbers always contains six numbers summing up to a multiple of $6$. This is a problem from a selection to IMO 2014. I like thinking about this problem, it is ...
1
vote
1answer
60 views

product of greatest common divisor

Given two numbers $m$ and $n$ how can we calculate the gcd product of any two numbers i.e, $\operatorname{gcd p}(n,m)=\gcd(n,1)\gcd(n,2)\cdots\gcd(n,m)$ where gcd is the greatest common divisor? Can ...
2
votes
0answers
55 views

Prove the following : [duplicate]

Prove the following : $$ {{n}\choose{7}}-\left \lfloor{\frac{n}{7}}\right \rfloor $$ is divisible by 7.
1
vote
1answer
85 views

How many regulars do the primorials 223092870 and 6469693230 have?

Regulars = Divisors + Semidivisors http://global.britannica.com/EBchecked/topic/496213/regular-number So for example: 6 has 5 regulars: 1, 2, 3, 4, 6. 8 has 4 regulars: 1, 2, 4, 8. 9 has 3 ...
0
votes
0answers
67 views

Among the superior highly composite numbers, which are the most divisor dense numbers?

I’m searching for the most divisor dense natural numbers. Firstly we have the highly composite numbers: 1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, … But ...
1
vote
3answers
71 views

Is x/x equal to 1

My question is whether $x/x$ is always equal to 1. I am mostly intersted in real numbers and particularly wonder whether $x/x$ is defined at $x=0$. On one hand the division should simplify to 1, on ...
2
votes
2answers
117 views

Asymptotic divisor function / primorials

Let $p_n\#\equiv\prod_{k=1}^{n}p_k$ (primorial), and $\sigma(n)=\sum_{d|n}^{}d$ (divisor function). Could someone please tell me what the general asymptotic of $\dfrac{\sigma(p_n\#)}{p_n\#}$ is? It ...
0
votes
1answer
28 views

For how many values of $a,b,c\in(1,2\ldots,p-1)$ does $p$ | $({a^2}-bc)$ where $p$ is an odd prime number

In a mock test for an entrance exam I am preparing for came the following question: Let $p$ be an odd prime number and $T_p$ be the following set of matrices $$ T_p= \left( ...
0
votes
2answers
26 views

Divisibility Problem: How can I solve this?

Suppose that $a,b,q,r$ are any integers such that $b > 0$ and $a = bq + r$, with $0\le r<b$, and suppose $b|a$. Must it be the case that $r = 0$? Justify your answer. Can anyone please let me ...
0
votes
1answer
43 views

Verify my proof on elementary number theory

I've tried to prove this theorem, which is very simple, but is a kind of practice for me. Let $a,b$ be two positive integers. Therefore, if $a+b$ is a composite number, $frac(\frac{a}{l}) + ...
0
votes
0answers
54 views

Vieta jumping with non-monic polynomials

I have recently discovered Vieta jumping as a problem-solving technique. In order to teach myself about it, I have located most (all of?) the standard references, both here on MSE and "out there" (via ...
0
votes
0answers
36 views

Moving up the Y axis the lengh of the hypotenuse of a right triangle

If i have a right triangle ABC with B being the right triangle and length AB = 50 and length BC = 50. Based on the Cartesian coordinate system if i wanted to move up the Y axis the length of the ...
0
votes
0answers
33 views

The elegant expression in terms of gcd and lcm - algebra - (2)

Definition: suppose a quantity $P$ is identified by $$ \frac{P}{k}\simeq \frac{P}{k}+1 $$ what we mean is that $$ P= 0\pmod{k}. $$ That means that when $P \to P+k$, then $$ \frac{P}{k}\to ...
2
votes
1answer
39 views

The elegant expression in terms of gcd and lcm - algebra

Given three positive integer numbers $k_1$, $k_2$, $k_3$, we may denote their greatest common divisor(gcd) by $\gcd(k_i,k_j)\equiv k_{ij}$ for gcd of a two pair of number $k_i,k_j$. ...
0
votes
1answer
26 views

$(x+b)^3\mid P(x)+a$ and $(x-a)^3\mid P(x)-a$

$a,b\in\mathbb{C}$, $b!=0$ I need to find all the polynomials $P$ of degree $5$ verifying: $ \begin{cases}(x+b)^3\mid P(x)+a\\ (x-b)^3\mid P(x)-a\end{cases} $ PS : there was en error, i fixed it ...
0
votes
2answers
86 views

How does $n!^2$ divide $(2n)!$? [duplicate]

How can I show that $(n!)^2$ divides $(2n)!$, where $n$ is a natural number? So far I've noticed that we can rewrite $\dfrac{(2n)!}{(n)!^2}$ as a combination and we know that combinations are always ...