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
vote
3answers
35 views

probability of divisibility by $5$ [duplicate]

Let $m,n$ be $2$ numbers between $1-100$ . what is the probability that if we select any two random numbers then $5|(7^m+7^n)$ . My attempt last digit should be $5$ or $0$ so $7$ powers follow the ...
0
votes
1answer
63 views

If a number is divisible by two others, then it's divisible by their lcm

Prove that if $c$ is a common multiple of $a$ and $b$, then $c$ is a multiple of $\operatorname{lcm}(a,b)$ Nobody in my class has found a way to do it. Whatever I try, I always come to the ...
-1
votes
3answers
33 views

Prove that for every positive integer, this polynomial is divisible by 8 [duplicate]

prove that: $$8\mid (n-1)n(n+1)(n+2)$$ I tried to simplify this expression but had no luck.
-1
votes
5answers
100 views

Prove that for every positive integer, this polynomial is divisible by 24. [closed]

Prove that: $$24\mid n^4 + 2n^3 - n^2 - 2n, \quad \forall n\in \mathbb{Z}^+$$ I tried to prove it, but had no luck.
3
votes
4answers
68 views

Induction for divisibility: $3\mid 12^n -7^n -4^n -1$

I must use mathematical induction to show that $a_{n} = 12^n −7^n −4^n −1$ is divisible by 3 for all positive integers n. Assume true for $n=k$ $a_{k} = 12^k -7^k -4^k -1$ Prove true ...
6
votes
1answer
156 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} - ...
2
votes
1answer
39 views

Are there names for any of these four classes of numbers related to divisors and totatives?

Are there names for any of these four classes of numbers related to divisors and totatives? A [insert name here] of $n$ is a positive integer $\leq n$ that isn't a divisor of $n$ and that can be ...
2
votes
2answers
55 views

Beginner Number Theory Proofs - Common divisors and multiples

I'm taking a mathematics class where we have learned some introductory number theory - but I am having trouble with the whole 'proving this and that' component (most of it lol). Particularly with ...
-1
votes
4answers
29 views

Greatest common divisor questions? [closed]

An integer d is a divisor of a ⇔ ____ | ____. Equivalently, d is a divisor of a ⇔ ____ mod ____ = _____. Is it possible for a divisor of a to be bigger than a? The first blank would be d|a, and I am ...
22
votes
1answer
659 views

One of any consecutive integers is coprime to the rest

After reading this question, I conjectured a generalization of it. Conjecture: Fix $k\in \mathbb N$. Then, for all $n\in \mathbb N$, one of $n+1,\ldots,n+k$ is coprime to the rest. I ...
2
votes
1answer
37 views

Finding the possible values of $\gcd(a^2,b)$

If $\gcd (a,b)=p\qquad p\text{ is a prime.}$ What are the possible values of $\gcd(a^2,b)$ I saw this solution: $a:=\alpha p,\qquad b:=\beta p,\qquad \gcd(\alpha,\beta)=1$ $(a^2,p)=(\alpha^2 ...
0
votes
2answers
108 views

How many positive integers between 100 and 999 inclusive are odd?

I found the answer to this in a pdf online but don't understand their method: Every 2nd number is odd. 1000 div 2 − 100 div 2 = 500 − 50 = 450 The method I thought I could use didn't work either. If ...
2
votes
2answers
65 views

How do I demonstrate that a polynomial of degree $2$ divides one of degree $n$?

Let $f$ and $g$ the polynomials $$f(x) = (x+1)^{2n-1}+(-1)^n(x+2)^{n+1}\qquad\text{and}\qquad g(x) = x^2 + 3x + 3$$ How do I demonstrate that $g$ divides $f$? I tried finding the roots of $g$ then ...
1
vote
1answer
40 views

Given an integer $n$ and relatively prime positive integer $a$ and $b$, show that exactly one of $n$ and $ab-a-b-n$ is expressible in the form $ax+by$

Given an integer $n$ and relatively prime positive integers $a$ and $b$, show that exactly one of $n$ and $ab-a-b-n$ is expressible in the form $ax+by$ for some non-negative integers $x$ and $y$. ...
1
vote
2answers
142 views

Help with understanding this proof in discrete mathematics?

This is the question and solution: Q: Prove that for any integer $a$, $2a + 1$ and $4a^2$ + 1 are relatively prime. A: Since $4a^2 + 1 = (2a − 1)(2a + 1) + 2$, any common divisor of $2a + 1$ and ...
53
votes
16answers
16k views

For any prime $p > 3$, why is $p^2-1$ always divisible by 24?

I know this is very basic and old hat to many, but I love this question and I am interested in seeing whether there are any proofs beyond the two I already know.
1
vote
2answers
65 views

Prove that $7 | (3^{2n + 1} + 2^{n +2})$

Prove that $7 | (3^{2n + 1} + 2^{n +2})$ So far I have: Base case: n = 1 $ = (3^{2(1) + 1} + 2^{(1) +2})$ $ = (3^{3} + 2^{3})$ $ = (35)$ which divides 7 Inductive Step: $ = (3^{2(n +1) + 1} + ...
13
votes
2answers
324 views

Prove that neither $A$ nor $B$ is divisible by $5$

Let the sum $$ {1+ \frac12 + \frac13 + \frac 14+ \dots +\frac1{99} + \frac 1{100}}$$ be written as $\frac AB$, where $A$ and $B$ are positive integers with no common factors. Show that neither $A$ ...
0
votes
2answers
41 views

finding the value of k in an equation

Find the value of k such that $f(x)=x^4-kx^3+kx^2+1$ is divisible by $d(x)=x+2$. I tried using synthetic division for this problem and was able to get up to the part where k ends up being$(17+8k)$. ...
1
vote
2answers
31 views

Divisibility problem. Prove or disprove if 𝑎|𝑏c, then 𝑎|𝑏 or 𝑎|𝑐

I understand the problem very well. I just don't how to go at it. Prove or Disprove: For all 𝑎, 𝑏, 𝑐 ∈ ℤ+, if 𝑎|𝑏c, then 𝑎|𝑏 or 𝑎|𝑐.
29
votes
1answer
359 views

A spiralling sequence based on integer divisors. Has anyone noticed this before?

Firstly, please excuse the informal style of my explanation, as I am not a mathematician, although I am aware that this can be explained in more formal terms. I have mapped integers to points on a ...
4
votes
0answers
37 views

Functional division $\max(f(x+y),f(x-y))\mid \min(xf(y)-yf(x), xy)$

As the title suggests, the problem here is: Find all functions $f:\mathbb{Z}\to\mathbb{N}$ such that, for every $x,y\in\mathbb{Z}$, we have $$\max(f(x+y),f(x-y))\mid \min(xf(y)-yf(x), xy)$$ I ...
0
votes
5answers
86 views

Let $a,b$ be relative integers such that $2a+3b$ is divisible by $11$. Prove that $a^2-5b^2$ is also divisible by $11$.

The divisibility for $11$ of $a^2 - 5b^2$ can be easily verified; in fact: $$a \equiv \frac {-3}{2}b \pmod {11}$$ therefore $$\frac {9}{4}\cdot b^2 - 5b^2 = 11(-\frac{b^2}{4}) \equiv 0 \pmod {11}.$$ ...
2
votes
3answers
161 views

How to prove the number is a prime?

A natural number $n$ has the property that if $d$ divides $n$ then $d+1$ divides $n+1$. Show that $n$ must be a prime.
3
votes
7answers
88 views

Prove that there are infinitely many integers n such that $4n^2+1$ is divisible by both $13$ and $5$

Prove that there are infinitely many integers n such that $4n^2+1$ is divisible by both $13$ and $5$. This can be written as: $$65k = (2n)^2 + 1$$ It's clear that $k$ will always be odd. Now I am ...
0
votes
1answer
48 views

proof - GCD and Number Theory

I have been trying to solve these but have had no success. Please help by giving hints not answers. Assuming that $\gcd(a,b)=1$ prove the following: (a) $\gcd(a+b,a-b)=1$ or $2$. [Hint: Let ...
0
votes
2answers
78 views

Divisibility problem involving the $2015^{th}$ power [closed]

Show that the number $$ (5+2\sqrt6)^{2015} + (5-2\sqrt6)^{2015} - 10$$ is divisible by $960$.
6
votes
5answers
119 views

Prove that the determinant is a multiple of $17$ without developing it

Let, matrix is given as : $$D=\begin{bmatrix} 1 & 1 & 9 \\ 1 & 8 & 7 \\ 1 & 5 & 3\end{bmatrix}$$ Prove that the determinant is a multiple of $17$ without developing it? ...
5
votes
2answers
45 views

If a, b, c are three natural numbers with $\gcd(a,b,c) = 1$ such that $\frac{1}{a}+\frac{1}{b}=\frac{1}{c}$ then show that $a+b$ is a square.

If a, b, c are three natural numbers with $\gcd(a,b,c) = 1$ such that $$\frac{1}{a} + \frac{1}{b}= \frac{1}{c}$$ then show that $a+b$ is a perfect square. This can be simplified to: $$a+b = ...
0
votes
1answer
61 views
0
votes
4answers
32 views

Why does dividing a number with $n$ digits by $n$ $9$'s lead to repeated decimals?

For example, $\frac{1563}{9999} = 0.\overline{1563}$. Why does that make sense from the way the number system works? I can vaguely see that since the number $b$ with $n$ $9$'s is always greater ...
2
votes
1answer
102 views

Prove that $a^n - b^n$ does not divide $a^n + b^n$ [duplicate]

Prove that $$a^n - b^n \text{ does not divide } a^n + b^n \text { and } a,b,n \in \mathbb{Z}^+. n > 1$$ I have tried to prove this but have had no success. My efforts till now were concerned ...
1
vote
3answers
108 views

Prove by induction that $3^n +7^n −2$ is divisible by $8$ for all positive integers $n$…

Prove by induction that $3^n +7^n −2$ is divisible by $8$ for all positive integers $n$. So far I have the base case completed, and believe I am close to completing the proof itself. Base ...
2
votes
4answers
31 views

Use the binomial theorem to prove if $m\mid b - a$, then $m \mid b^n - a^n$.

I'm trying to prove that if $m\mid b - a$, then $m \mid b^n - a^n$. I have done it several ways so far, including through induction and through the application of theorems regarding congruence (i.e. ...
0
votes
4answers
117 views

Palindromes on Keypad and divisibility by $111$ [closed]

The integers 1 through 9 are arranged as follows on a rectangular keypad: $\begin{array}{c c c} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9 \end{array}$ Consider the 6-digit ...
0
votes
1answer
20 views

Elementary proof: division by integer makes real number smaller.

It's been so long since I took discrete math, maybe someone here can help me with what ought to be a straight forward and simple proof. Effectively I want to show this: Let a and b be positive ...
0
votes
1answer
34 views

Is it possible to know if $X$ is divisible by $Y$ without dividing $X$ by $Y$.

Background I am working on a project involving FPGA's (a configurable logic circuit) and modulus of numbers to determine if $X$ is divisible by $Y$. When I take the modulus of a number a full ...
0
votes
0answers
33 views

Is this correct? Prove n+3 is not divisible by 5 using proof by contradiction

Let $n=5k$, $n$ and $k$ are integers. I will assume $n+3$ is divisible by $5$ which means there is an $m$ such that $n+3=5m$. Now, $n+3-3=5m-3$, i.e. $n=5m-3$. We know that $n$ is divisible by $5$ ...
0
votes
1answer
50 views

Easy way to divide $2^{1000}$ by $59$ [closed]

What will be the remainder when $2^{1000}$ is divided by $59$? What is the easiest way to calculate this?
1
vote
3answers
71 views

Is there a term that is divisible by $67$, in the sequence $10, 110, 1110, 11110, …$

Consider the sequence $10, 110, 1110, 11110, 111110, ...$ Here the $n$ the term $a_n=\sum \limits_{k=1}^n\left(10^k\right)$ Is there a term which is divisible by $67$ ? How can we show that?
5
votes
2answers
78 views

show that $2^k|n\Longleftrightarrow 2^k|a_{n}$

Let sequence $\{a_{n}\}$ such $a_{0}=0,a_{1}=1,a_{n}=2a_{n-1}+a_{n-2}$. show that $$2^k|n\Longleftrightarrow 2^k|a_{n}$$ I try to find the $\{a_{n}\}$ closed form ...
1
vote
1answer
40 views

Subsets and Divisibility

What is the size of the largest subset, S, of {1,2,...2013} such that no pair of distinct elements of S has a sum divisible by 3? So...I know the very basic divisibility by 3 rule that any number ...
2
votes
2answers
59 views

How do people come up with divisibility tests?

For example, the test for divisibility by $2$ is quite obvious. But I am quite intrigued by the others, particularly $3$, $7$ and $11$. Also I have come across tests for numbers as far as $50$. How do ...
2
votes
6answers
91 views

Prove that $n(n+1)(n+5)$ is a multiple of $6$

I need to prove that $n(n+1)(n+5)$ is divisible by 6. where $n$ is a natural number. I have used the method of induction. But not successful I got the expression $(k^3+6k^2+5k)+3k^2+15k+12$ when ...
0
votes
4answers
71 views

Prove that if a|bc then a|b or a|c for a, b, c positive integers where a is not zero [closed]

Prove or disprove (by providing a counter-example) that if a|bc then a|b or a|c for a, b, c positive integers where a is not zero.
5
votes
4answers
6k views

How to prove $\gcd(a,\gcd(b, c)) = \gcd(\gcd(a, b), c)$?

I am trying to prove that $\gcd(a, \gcd(b, c)) = \gcd(\gcd(a, b), c)$. The definition of GCD available to me is as follows: Given integers a and b, there is one and only one number d with the ...
1
vote
1answer
19 views

Find the remainder and quotient when we will divide $a$ by $q$

When we divide $a$ by $b$ we get remainder $r=10$ and quotient $q=7$ What will be the remainder and quotient when we will divide $a$ by $q$? My attempt: $$a=b\cdot ...
2
votes
1answer
53 views

How to prove that $(p^2)!$ is divisible by $(p!)^{p+1}$?

For each prime $p$, find the greatest natural power of $p!$, which divides the number $(p^2)!$ ($n!=1 \cdot 2 \cdot ...\cdot n$) My work so far: 1) $p=2 \Rightarrow p!=2; (p!)^2=4!=24 \vdots 8=2^3$. ...
0
votes
3answers
38 views

Which is more; even or odd positive factors?

Suppose $f(n)=$ $\{$ ( number of $n$'s positive even factors) $-$ (number of $n$'s positive odd factors) $\}$ How can we prove/disprove the below statement? $f(n)< 0 $ for half or more ...
13
votes
6answers
2k views

Proof: if $p$ is prime, and $0<k<p$ then $p$ divides $\binom pk$ [duplicate]

Question : If $p$ is prime, and $0< k< p$ show that $ p \mid {p \choose k}$ ${p \choose k}$ can be rewritten as: $${p(p-1)(p-2)\dots(p-(k-1))(p-k)! \over (p-k)!\cdot ...