This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.

learn more… | top users | synonyms

4
votes
0answers
62 views

Systems of linear modular equations with unknowns in the moduli

I am interested in systems of linear modular equations, where the unknowns also appear in the moduli. The general form would be: $A \vec{x}= \vec{b} \;\textrm{mod} \; (C \vec{x}+\vec{d})$ where A ...
19
votes
3answers
2k views

Prove that there exists a number divisible by 1999 with digit sum 1999

My nephew in the secondary school asked me how to solve the problem as stated in the title. Honestly, I do not have any idea how to do it: Prove that there exists a positive integer number such ...
0
votes
3answers
90 views

Do odd numbers have only odd divisors?

Is it true, that odd numbers have only odd divisors? If yes, what would a formal proof look like?
0
votes
3answers
59 views

For numbers divisible by three, why is the sum of their digits able to be divided by three? [duplicate]

When you add the digits of any number that is divisible by three, that sum of those digits also appears to be divisible by three (with no remainder). For example a number (which I randomly grab from ...
1
vote
1answer
40 views

Prove that $\begin{pmatrix} 2n \\ n \end{pmatrix}$ is not divisible by $p$

Let $n$ be an integer greater than $5$. I would like to prove that if $p$ is a prime such that $\displaystyle \frac{2}{3}n < p \leq n$ then $\displaystyle \begin{pmatrix} 2n \\ n \end{pmatrix}$ is ...
0
votes
1answer
25 views

Isolating Decimals

I'm in need of isolating the decimal part of a number using maths only, no excel functions or anything like that, but it's proving to be much harder than I thought it would be. For example, I have ...
3
votes
1answer
87 views

The value of $\gcd(2^n-1, 2^m+1)$ for $m < n$

I've seen this fact stated (or alluded to) in various places, but never proved: Let $n$ be a positive integer, let $m \in \{1,2,...,n-1\}$. Then $$\gcd(2^n-1, 2^m+1) = \begin{cases} 1 ...
1
vote
3answers
18 views

Remainders and modulars

How do I find the remainder of $3^{2002}$ divided by $5$ using mod? I can solve the remainder of, for example, $7^{220}$ divided by $8$ because $7=-1 \pmod 8$, but that doesn't work here.
1
vote
1answer
39 views

Showing existence in proof of Division Algorithm using induction

Division Algorithm: Let $a$, $b$ $\in \mathbb{Z}$ be any integers and $b \neq 0$. Then, $\exists$ unique integers $q$, $r$ such that $a = bq + r$ and $0 \leq r < |b|$. I am trying to show ...
1
vote
1answer
84 views

Show that there exist infinitely many $i$ such that $a_i-1$ is divisible by $2^{2015}$

Let $(a_n)$ be a sequence defined by: $a_o=2, a_1=4, a_2=11$ and $\forall n \geq 3$, $$a_n = (n+6)a_{n-1}-3(2n+1)a_{n-2}+9(n-2)a_{n-3}$$ Show that there exist infinitely many $i$ such that $a_i-1$ is ...
0
votes
3answers
61 views

Euclid's proof on the infinity of primes

Could someone shed some light on this? I perfectly understand Euclid's proof on the infinity of primes. Let's suppose there is a largest prime, p, and then let's make a number, n, so that n = (2 x 3 ...
0
votes
2answers
49 views

$n>k>0$ are integers , then among the integers $n , n+1 , …, n+k-1$ , there is an integer containing a prime divisor greater than $k$ ? [closed]

If $n>k>0$ are integers , then how to show that among the integers $n , n+1 , ..., n+k-1$ , there is an integer containing a prime divisor greater than $k$ ?
2
votes
1answer
46 views

$2(n-2)+1$ does not divide $(n-2)(n-3)/2$ for $n \ge 8$

For $n \ge 8$ the number $2(n-2)+1$ never divides $(n-2)(n-3)/2$. Any ideas how to prove this? I see that $(n-2)(n-3)/2 = 1 + 2 + \ldots + (n-3)$. If I suppose that $2(n-2)+1$ divides ...
3
votes
3answers
121 views

Prove that $\sqrt{3}$ is not a rational number [duplicate]

There is a similar question however that question asks why $3 |p^2$. Here the question is about $ 3 | p^2 \rightarrow 3 | p$. It is a simple exercise (1.2.1) from Abbot's "Understanding Analysis". ...
0
votes
4answers
110 views

Is it correct that $\frac{1}{0}=\frac{1}{-0}$ and if it is, why is $\frac{1}{0} \neq 0$?

This is a genuine question, I am not trying to convince anyone. But I'm sure hundreds of people already considered this, so if you can point out where I'm wrong, it would be much appreciated. If we ...
1
vote
2answers
48 views

Proof for elementary divisibility problem

Not sure if my thinking is correct. For the problem "$a$ divides $b$ if and only if $a$ divides $b^2$." So far my proof goes: since $a$ divides $b$ there exists an integer $n$ such that $b=an$. Then ...
3
votes
0answers
38 views

Prove that $2\mid x$ and $5\mid x$ if and only if $10\mid x$

I have to do it without using Fundamental Theorem of Arithmetic. Can someone check my work? Prove if $2\mid x$ and $5\mid x$, then $10\mid x$. Let $x \in \mathbb{Z}$. Suppose $2\mid x$ and $5\mid ...
7
votes
6answers
249 views

If $ a + b + c \mid a^2 + b^2 + c^2$ then $ a + b + c \mid a^n + b^n + c^n$ for infinitely many $n$

Let $ a,b,c$ positive integer such that $ a + b + c \mid a^2 + b^2 + c^2$. Show that $ a + b + c \mid a^n + b^n + c^n$ for infinitely many positive integer $ n$. (problem composed by Laurentiu ...
3
votes
0answers
87 views

$1+2^x+\ldots+n^x \mid 1+2^y+\ldots+n^y$ for all $n$ implies $x=y$?

The following problem was proposed by A. Schinzel a couple of days ago at the 22nd Conference on Number Theory, held in Liptovsky Jan (Slovakia). He pointed out that the question has an affirmative ...
0
votes
5answers
140 views

Mathematical induction: $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ [duplicate]

Prove that $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ where $n$ is a nonnegative integer. I have seen many questions on this site that contain the answer to this problem and I already know the solution, ...
-1
votes
3answers
79 views

Using induction to prove that $2 \mid (n^2 − n)$ for $n\geq 1$

Use induction to prove that, for all $n \in \mathbb{Z}^+$, $2\mid (n^2 − n)$. That is, I am supposed to use induction to prove that $(n^2 − n)$ can be divided by $2$ when $n$ is a positive ...
4
votes
5answers
92 views

How can I prove that $2^{n+2}\mid(2n+3)!$?

I'm not sure where to proceed or how to go about proving this assertion holds for all natural numbers n: $$2^{n+2} \mid(2n + 3)!$$ The base case is $n=1$, where $2^{1+2}\mid(2\cdot 1+3)!$ which ...
0
votes
4answers
43 views

Show that 2|n(n+1) using induction [duplicate]

Show that 2|n(n+1) using induction I tried but im stuck , it still (n+1)(n+2) Two successive numbers It's simple using the the methode that n=2k or n=2k+1 Can someone help or give a hint ?
1
vote
7answers
351 views

Proving by strong induction that $\forall n \ge 2, \;\forall d \ge 2 : d \mid n(n+1)(n+2)…(n+d-1) $

I'm trying to prove by induction the following statement without success: $$\forall n \ge 2, \;\forall d \ge 2 : d \mid n(n+1)(n+2)...(n+d-1) $$ For the base case: $n = 2$, $d = 2$ $2\mid 2(2+1)$ ...
2
votes
1answer
81 views

Is it possible for $(900q^2+ap^2)/(3q^2+b^2p^2)$ to be an integer?

The original problem is: "Find all possible pairs of positive integers $(a, b)$ $$k = \dfrac{a^3+300^2}{a^2b^2+300}\tag1$$ such that $k$ is an integer." I've tried so many different ways. Now this ...
-4
votes
1answer
70 views

Suppose $a$, $b$, and $c$ are integers. Prove that if $a \mid b$ and $a \mid c$, then $a \mid (b +c)$ [duplicate]

Suppose $a$, $b$, and $c$ are integers. Prove that if $a \mid b$ and $a \mid c$, then $a \mid (b +c)$
1
vote
1answer
39 views

Does there exist positive integers $a,b,n$ , where $n>1$ , such that $a^n - b^n |a^n + b^ n$ ?

Does there exist positive integers $a,b,n$ , where $n>1$ , such that $a^n - b^n |a^n + b^ n$ ? ; the only trivial thing I can see is that if so happens , then $a^n - b^n | 2b^n$ , but nothing else ...
4
votes
2answers
30 views

$a,b$ be two positive integers , where $b>2 $ , then is it possible that $2^b-1 \mid 2^a+1$?

If $a,b$ be two positive integers , where $b>2 $ , then is it possible that $2^b-1\mid2^a+1$ ? I have figured out that if $2^b-1\mid 2^a+1$, then $2^b-1\mid 2^{2a}-1$ , so $b\mid2a$ and also $a ...
4
votes
0answers
128 views

Connections between Fibonacci and natural numbers

Here are some known facts about the Fibonacci numbers and then some questions regarding them . 1.Carmichael's theorem : For every $n>12$ $F_n$ has a prime divisor which doesn't divide any of ...
1
vote
3answers
2k views

The least perfect square, which is divisible by each of 21,36 and 66 is (options)

(a) 213444 (b) 214344 (c) 214434 (d) 231444 Any short method to solve this question in 1 min?
2
votes
2answers
90 views

Prove $p$ is prime

Let $p$ be an integer with this property: whenever $b, c \in \mathbb Z$ such that $p\mid bc$, then $p\mid b$ or $p \mid c.$ Prove $p$ is prime. Here is my attempt at a proof: Suppose $d \mid p$. Then ...
0
votes
2answers
66 views

$b$ divides $a \Leftrightarrow -b$ divides $a$

Prove that $b$ divides $a$ if and only if $-b$ divides $a$. I'm thinking something like $a = bp$ and $b = aq$, then go on from there? It seems simple enough but thanks for the help in advance!
1
vote
0answers
19 views

If $a, b, c, d \in \mathbb Z$ and $p$ is a prime factor of $a - b$ and $c - d$, then $p$ is a prime factor of $(a + c) - (b + d)$

By hypothesis, $p \mid (a - b), (c - d)$. Then $p \mid [(a - b) + (c - d)]$. In other words, $p \mid [(a + c) - (b + d)]$. Does it work?
0
votes
2answers
43 views

Number of divisors $d$ of $n^2$ so that $d\nmid n$ and $d>n$

I just wanted to share this nutshell with you guys, it is a little harder in this particular case of the problem: Find the number of divisors $d$ of $a^2=(2^{31}3^{17})^2$ so that $d$ does not ...
0
votes
2answers
97 views

Proof that expression is integer, $\frac{(2n)!}{n!(n+1)!}$

can you help me with this excercises.. Proof that expression is integer, $$\frac{(2n)!}{n!(n+1)!}$$ I've tried for induction!! $p(1):\frac{(2)!}{2}=1 $ for $p(k)=\frac{(2k)!}{k!(k+1)!}$ for ...
1
vote
2answers
40 views

Number 9 and age of mother when child is born.

If a mother's age is divisible by 9 when a child is born then once you go to the next decade,n every 11 years the child's age and mother's age are always the same two numbers in reverse order. For ...
2
votes
3answers
133 views

If $\gcd(ab,c)=d$ and $c|ab$ then $c=d$

For all positive integers $a$, $b$, $c$ and $d$, if $\gcd(ab, c) = d$ and $c | ab$, then $c = d$. Need help proving this question, I know that $abx + cy = d$ for integers $x,y$ and that $c|ab$ can be ...
1
vote
2answers
144 views

Divisibility and GCD proof

I'm having trouble with this simple proof. Any help would be appreciated. I don't really know where to start to try to conquer this problem. Suppose $a|m$, $b|m$ and $\gcd(a,b) = 1$. Prove, ...
0
votes
1answer
31 views

If $a, b \mid c \text { and } \gcd(a, b) = d, \text { then } ab \mid cd $

$a \mid c \to c = ak \text { and } b \mid c \to c = bj.$ $ak + bj = 2c = d \to c \mid d.$ $d \mid a \to a = dj.$ $c = ak = d(jk) \to d \mid c.$ So, $c = d.$ $a \mid c \text { and } b \mid c ...
2
votes
0answers
36 views

About the least common multiple of numbers and combinatorial

Prove that for any positive integer $n$, the least common multiple of the numbers $1, 2, 3, \ldots , n$ and the least common multiple of the numbers: ${n\choose 1}, {n\choose 2}, \ldots , {n\choose ...
2
votes
1answer
114 views

Difficult sets of Equations, counting

Let $ m$ be the number of solutions in positive integers to the equation $ 4x+3y+2z=2009$, and let $ n$ be the number of solutions in positive integers to the equation $ 4x+3y+2z=2000$. Find the ...
11
votes
0answers
256 views

Dividing the whole into a minimal amount of parts to equally distribute it between different groups.

Suppose we have a finite amount of numbers $x_1, x_2, ..., x_n$ ($x_i\in\mathbb{N}$) and an object that should be divided into parts in such a way that it can be without further dividing distributed ...
4
votes
1answer
58 views

Missing values of the ratio $\frac{(x+y+z)^2}{x^2+y^2+z^2}$

Let $x,y,z$ be some positive integers. Is it true that we cannot find any positive integer $n$ for which $$ \frac{(x+y+z)^2}{x^2+y^2+z^2}=1+\frac{2}{3n}\,\,? $$
2
votes
2answers
65 views

For what values of $n$ , does $7 \mid 5^n+1$

$7 \mid 5^n+1$ implies $5^n+1=7a$ for some integer $a$ i.e $5^n=7a-1$ Now , $5^n$ is an integer which always ends with $5$ [for any integer $n$]. Thus , $7a-1$ must also end with $5$.But , this is ...
5
votes
0answers
221 views

A natural number has exactly 10 divisors including 1 and itself.How many distinct prime factors can this natural number have?

A natural number has exactly 10 divisors including 1 and itself.How many distinct prime factors can this natural number have? options given: (a) either $1$ or $2$ (b)$1$ or $3$ (c)either $2$ or ...
0
votes
4answers
127 views

Why Zero divided by Zero is undefined and not Infinity [duplicate]

apologize in advance if this is a duplicate, but I found a lot questions related to this but none answering this specific question. My logic is: let's consider division the opposite of ...
3
votes
3answers
161 views

when ${\rm gcd} (a,b)=1$, what is ${\rm gcd} (a+b , a^2+b^2)$? [duplicate]

I want to prove above statement "what is ${\rm gcd} (a+b , a^2+b^2)$ when ${\rm gcd}(a,b) = 1$" I've seen some proofs of it, but i couldn't find useful one. here is one of the proof of it. some ...
-1
votes
2answers
53 views

How to find $\frac{a+b+c}x$? [closed]

$ab$ and $bc$ are two digit numbers. if $ab*x=2 $ and $bc*x=3$ then find $\frac{a+b+c}x$. (* is multiplication) It looks simple but I couldnt go further. $$17b=2(15a-c)\iff b\mid2 \quad and\quad ...
1
vote
3answers
1k views

Show that the gcd of an odd integer and an even integer is odd

I am using the definition of odd and even integers along with bezout's theorem and I end up with something of the form $d=(2k)m+(2l+1)p$ where $a=2k$ and $b=2l+1$. I've tried to use contradiction as ...
3
votes
1answer
76 views

Each number in a subset $S\subseteq \{1,\ldots,2n\}$ does not divide another one. Then $\max |S|$?

This problem comes from a seemingly innocuous question from a professor during a lesson for a Math Olympiad course. [A part of this question is really a classic of number theory/combinatorics] ...