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

learn more… | top users | synonyms

2
votes
2answers
62 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
139 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 ...
52
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
60 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
313 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
40 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
29 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
344 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 ...
1
vote
3answers
88 views

Divisibility by 4 (induction proof)

We have to show that $$ n^4 -n^2 $$ is divisible by 3 and 4 by mathematical induction Proving the first case is easy however I do not know how what to do in the inductive step. Thank you.
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}.$$ ...
1
vote
3answers
159 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
87 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
77 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
117 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
31 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
99 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
101 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
33 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
77 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
33 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
58 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
90 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
61 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 ...
2
votes
0answers
55 views

Prove or disprove $a^2\mid b^3\Longrightarrow a\mid b$

I need to prove or to give a counter-example: $$a^2\mid b^3\Longrightarrow a\mid b$$ My attempt: First, let's check with small integres,trying to find counter-example: $2^2\mid ...
2
votes
4answers
100 views

Prove or disprove $d\mid (a^2-1)\Longrightarrow d\mid (a^4-1)$

I need to prove or to give a counter-example: $$d\mid (a^2-1)\Longrightarrow d\mid (a^4-1)$$ My attempt: Yes, this is correct, First: $(a^2-1)=(a-1)(a+1)\\ (a^4-1)=(a-1)(a+1)(a^2+1)$ If ...
0
votes
1answer
43 views

The primes $2s+1$ with the constraint that $s$ satisfy certain congruence relations and Euler's idoneal numbers.

I would like to prove the following statement: If $s>1$ is a positive integer and $s\equiv0$ modulo 3 and $s\equiv0$ modulo 4 and $2s+1$ is prime then $2s+1 = x^{2}+24y^{2}$ for some ...
0
votes
2answers
71 views

Can a product of 4 consecutive natural numbers end in 116

So i was given this question with two parts: (a) Prove that the product of two consecutive even numbers is always divisible by 8. (b) Can a product of 4 consecutive natural numbers end in 116? For ...
0
votes
1answer
25 views

Confused about a simplification step in induction

Hello - I don't know how they got from the 3rd line to the 4th line. I understand all other parts of the simplification.
0
votes
1answer
35 views

Reference request for a divisibility property of Fibonacci numbers

Define the Fibonacci numbers $F_n$ by $F_n=F_{n-1}+F_{n-2}$ and initial values $F_0=0$ and $F_1=1.$ I would like to get a reference for the following result: If $p$ is a prime number with $p \equiv ...
13
votes
7answers
747 views

How can I find the possible values that $\gcd(a+b,a^2+b^2)$ can take, if $\gcd(a,b)=1$

If $\gcd(a,b)=1$, how can I find the values that $\gcd(a+b,a^2+b^2)$ can possibly take? I can't find a way to use any of the elemental divisibility and gcd theorems to find them.
1
vote
4answers
514 views

Suppose $(a,b)=1$, then $(2a+b,a+2b)=1\text{ or }3$.

Suppose $(a,b)=1$. Let $d=(2a+b,a+2b)$. Then $d=(2a+b)u+(a+2b)v=a(2u+v)+b(2v+u)$ where $u,v \in \mathbb{Z}$. Since $(a,b)=1$, then $a(2u+v)+b(2v+u)=1$. I'm not sure if I'm going in the right ...
1
vote
2answers
43 views

Let $k = (a+b,a^2+b^2-ab)$. If $(a,b)=1$ then $k = 1$ or $k=3$.

Yes, I know that this questions has two answers, but I can't see why $k$ can't be 27, or any other $3^n$ with $n \neq 2$.
0
votes
1answer
50 views

$\gcd( x+y, x^2 - xy + y^2) $ is 1 or 3 for coprime $x$, $y$ [duplicate]

How does one show that: if $\gcd( x, y) = 1$, then $\gcd( x+y, x^2 - xy + y^2) = 1\,{\rm or }\,3$.
3
votes
2answers
2k views

If $\gcd(a,b)=1$, then $\gcd(a+b,a^2 -ab+b^2)=1$ or $3$.

Hint: $a^2 -ab +b^2 = (a+b)^2 -3ab.$ I know we can say that there exists an $x,y$ such that $ax + by = 1$. So in this case, $(a+b)x + ((a+b)^2 -3ab)y =1.$ I thought setting $x = (a+b)$ and $y = ...