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)

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?
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
vote
1answer
171 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
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 ...
-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$.
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 ...
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
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 ...
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 ...
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
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
2answers
77 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
42 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
69 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
61 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
70 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
73 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
122 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
44 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
60 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
37 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
42 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
87 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 ...
2
votes
1answer
44 views

Properties of Integers

A theorem presented in my discrete math book. Let $d$ be the smallest positive integer of the form $ax + by$. Then $d = \gcd(a,b)$, where gcd means greatest common divisor. I don't understand ...
3
votes
1answer
59 views

How to show $(n-1)^3n^3(n+1)^3$ is divisible by 7 and 9?

Yeah it looks like a basic, really elementary question, but i'm having hard time with it. First i tried to show that it's divisible by 9 $$(n-1)^3n^3(n+1)^3 = ((n+1)(n-1))^3n^3 = (n^2-1)^3n^3 = ...
0
votes
1answer
35 views

Number Theory Divisibility Question

(From Math Challenge II Number Theory packet) Given that $a,b,n$ are positive integers. Assume that for any positive integer $k\neq b, (k-b)\mid(k^n-a)$, the which of the following must be true? ...
0
votes
0answers
18 views

WordProblem on factors and remainder theorem

Mr.Chaalu while travelling by Ferry queen has travelled the distance one Kilometer more, than the fare he paid per km. Initially he had total amount of Rs.350/- in his wallet. Now he is only left with ...
7
votes
1answer
61 views

Prove that $n$ is divisible by $6$

Problem: Let $x^2+mx+n$ and $x^2+mx-n$ give integer roots where $(m,n)$ are integers. Show that $n$ is divisible by $6$ My attempt: Since the roots are integers then the discriminants of both the ...
1
vote
2answers
63 views

How to prove that at least one of $a,b,c,d$ is not divisible by $ad-bc$ if $ad-bc>1$?

we have $ad-bc >1$ is it true that at least one of $a,b,c,d$ is not divisible by $ad-bc$ ? Thanks in advance. Example: $a=2$ , $b = 1$, $c = 2$, $d = 2$, $ad-bc = 2$ so $b$ is not divisible by ...
0
votes
2answers
51 views

If a natural number $x$ is divisible by $3$

Is the sentence If a natural number $x$ is divisible by $3$ then, if it is not divisible by $3$ then it is divisible by $5$ true or false?
0
votes
2answers
58 views

Divisibility of sum of powers: $\ 323\mid 20^n+16^n-3^n-1\ $ for which $n?$

I found this question in my Math Challenge II Number Theory packet: Find all positive integers $n$ that satisfy $323|20^n+16^n-3^n-1$. I don't even have any idea how to approach this question. Any ...
1
vote
4answers
105 views

How to solve the equation $n^2 \equiv 0 \pmod{584}$?

Well, I've confused when trying to solve this equation can anybody help me : $n^2 \equiv 0 \pmod{584}$ I tried to factorize the $584$ i got $584=2^3\times73$. so $n^2$ has to be divisible by $2^3$ ...
2
votes
1answer
67 views

Factors of a perfect square plus one

For large integer $a$, small integer $d$, consider the following quantity: $$a^2+d$$ What are the best lower bounds one can get for the sum $l+m$, where integers $l,m$ are such that: $$lm=a^2+d$$ ...
0
votes
2answers
36 views

Remainder question with $6!$ and 7

Find the remainder when $6!$ is divided by 7. I know that you can answer this question by computing $6! = 720$ and then using short division, but is there a way to find the remainder without using ...
1
vote
0answers
27 views

Using $ \gcd(a,b) = \gcd(b,r) $ if $ a \equiv r \pmod b$ for GCD?

It should be true that $\gcd(a,b) = \gcd(b,r) $ if $ a \equiv r \pmod b$. But: How can I use this equality to compute the GCD of $a$ and $b$? It seems as if $r$ is of the form $r = k\cdot b + s$ ...
1
vote
2answers
23 views

Divisibility question

I didn't understand how they reached at this conclusion: If $b\mid x-y$, $b\in \mathbb{N}$, $b\geq 2$ In this inequation: $$-(b-1)\leq x-y\leq b-1$$ The only integer divisible by $b$ is zero. (Why ...
0
votes
1answer
67 views

Pythagorean quadruple generators with a gcd relation

For non-negative integers $m,n,q,p$ with $\gcd(m,n,q,p)=1$, assume we have: $$\gcd(mq+np,b)=|nq-mp|$$ for some integer $$b<mq+np$$ and that $$8\nmid\,mq+np,$$ $$m+n+p+q\equiv 1\mod 2.$$ Can ...
1
vote
1answer
53 views

Greatest Common Divisor Divisibility Question

Can we characterize the pairs of positive integers $b<a$ such that: $b|(a^2+\gcd(a,b))$
4
votes
5answers
123 views

To find relatively prime ordered pairs of positive integers $(a,b)$ such that $ \dfrac ab +\dfrac {14b}{9a}$ is an integer

How many ordered pairs $(a,b)$ of positive integers are there such that g.c.d.$(a,b)=1$ , and $ \dfrac ab +\dfrac {14b}{9a}$ is an integer ?
2
votes
2answers
86 views

Why define $\gcd(r,s)$ as a positive generator $d$ of the cyclic group $H=\{nr+ms|n,m\in\mathbb{Z}\}$?

This is in regards to definition 6.8, p. 62 from Fraleigh's "A first course in abstract algebra". 6.8 Definition Let $r$ and $s$ be two positive integers. The positive generator $d$ of the ...
2
votes
3answers
41 views

Prove that if m is prime and m|kl then either m|k or m|l.

Proofs homework question, here's what I've figured out thus far. Suppose m doesn't divide k. We need to then prove that m|l. If m doesn't divide k and m is a prime then we know m and k are co-prime ...