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
1answer
87 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.
2
votes
1answer
69 views

How to calculate “gcd product” $\operatorname{gcdp}(n,m)=\gcd(n,1)\gcd(n,2)\cdots\gcd(n,m)$

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
56 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
96 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
111 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
101 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
134 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
30 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
29 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
49 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}) + ...
1
vote
0answers
149 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
46 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
46 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
44 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
28 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
101 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
60 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
44 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
1answer
53 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
71 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
66 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 ...
-1
votes
2answers
56 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
63 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
107 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
121 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
39 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
25 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
78 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
59 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
181 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
117 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
45 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 ...
0
votes
4answers
82 views

How to prove that if a number is divisible by two other numbers, then it is divisible by there product

I would like to prove if $a \mid n$ and $b \mid n$ then $a \cdot b \mid n$ for $\forall n \ge a \cdot b$ where $a, b, n \in \mathbb{Z}$ I'm stuck. $n = a \cdot k_1$ $n = b \cdot k_2$ $\therefore a ...
1
vote
0answers
53 views

GCD of this polynomial

So here is the exact question that i am having trouble on: "Extend the Euclidean algorithm to polynomials and find the greatest common divisor of: $3x^5-10x^4-4x^3-14x^2-7x-4$ and ...
1
vote
2answers
125 views

A puzzle on elementary number theory

I have been stuck with the following puzzle for some time. I could not prove it, nor could I find a counter example. I would be grateful to get some help on this.
1
vote
3answers
51 views

How to find exponent of a number in a combination?

How do I find the exponent of $7$ in $^{100}C_{50}$ that is, $\dfrac{100!}{(100-50)!\cdot 50!} =\dfrac{100!}{50!\cdot 50!}$, this question was out of the blue, and I haven't been able to find any ...
0
votes
6answers
133 views

If $n$ is a perfect square and a perfect cube then $7$ divides $n(n-1) $

If a positive integer $n$ is both a perfect square and a perfect cube , then is it true that $7$ divides $n(n-1)$ ?
1
vote
2answers
77 views

Solving a problem with a diophantine equation without trial and error.

I have the following problem: A teacher bought toys for the students of an academy, every toy for a boys costs $290$ and every toy for a girl costs $330$. If he spends $24300$, how many of each ...
0
votes
1answer
16 views

A question about divisibility

I'd like to check if what I did here is ok just in case. I'm asked to find the remainder of $a^2-3a+11$ knowing that the remainder of dividing $a$ by $18$ is $5$. What I did: The problem states ...
1
vote
2answers
71 views

Prove: $\text{if }a,b,c\in\mathbb{Z} \text{ and } a^2+b^2=c^2\text{ then }3\mid ab$

This is for a homework assignment. I am supposed to prove, $$\text{if }a,b,c\in\mathbb{Z} \text{ and } a^2+b^2=c^2\text{ then }3\mid ab$$ I've tried using direct proofs and proofs by contrapositive, ...
1
vote
3answers
332 views

Use mathematical induction to prove that $(3^n+7^n)-2$ is divisible by 8 for all non-negative integers.

Base step: $3^0 + 7^0 - 2 = 0$ and $8|0$ Suppose that $8|f(n)$, let's say $f(n)= (3^n+7^n)-2= 8k$ Then $f(n+1) = (3^{n+1}+7^{n+1})-2$ $(3*3^{n}+7*7^{n})-2$ This is the part I get stuck. Any help ...
1
vote
2answers
40 views

How to prove divisibility of the difference between two numbers.

Recently I have come across a statement saying that if $x$ and $y$ are divisible by $a$, then $x - y$ is also divisible by $a$. How can I prove this? Does it also apply to sum of $x$ and $y$ ?
0
votes
3answers
24 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
119 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 ...
0
votes
2answers
66 views

Divisibility exercise

Now, I have an idea how to attempt this question with modulo arithmetic, but I was thinking if there was a solution that did not involve modular arithmetic. If $7 |(b^2+c^2)$ iff $7|b$ and $7|c$. I ...
1
vote
2answers
31 views

$3^a\mid s(n) \Rightarrow 3^a\mid n$

This is not a homework question, neither a championship problem (as far as I've searched in the net), and it came up noticing a singular pattern, involving the powers of $3$: "Prove or disprove that ...
3
votes
3answers
238 views

A polynomial with integer coefficient

I'm struggling with this question: Suppose $P(x)$ is a polynomial with integer coefficients such that non of the values $P(1),...,P(2010)$ is divisible by $2010$. Prove that $P(n)\neq 0$ for all ...
2
votes
3answers
33 views

Show that $x_0$ must be an integer. Conclude that $\sqrt[n]{2}$ is irrational for every $n \geq 2$

I have a problem in my workbook that is as follows: Let $f = x^n + a_{n-1}x^{n-1}+\dots+a_1x+a_0 = 0 $ with $a_i \in \mathbb{Z}$. Suppose there exists a rational number $x_0$ with $f(x_0) = 0$. ...