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

learn more… | top users | synonyms

0
votes
1answer
44 views

$GCD(2^m-1,2^n-1)$ [duplicate]

Given $GCD(m,n)=d\ $ show that: $GCD(2^m-1,2^n-1)=2^d-1$ Suppose that $$\ GCD(2^m-1,2^n-1)=k\ $$ $$ \Rightarrow k|2^m-2^n=2^n(2^{m-n}-1),\ (assuming\ \ m>=n) $$ It's obvious that k is odd and we ...
1
vote
1answer
15 views

Prove variant of the division algorithm

The Division Alogrithm states that $\forall a, b \in \mathbb{N}$ where $b \neq 0$, $ \exists q,r\in \mathbb{N}$ such that $a=qb+r$ with $0 \leq r \lt b$. And one of the ways to prove it is to set $$ S ...
1
vote
2answers
52 views

Problem involving factorials (divisibility) [closed]

Show that, for every $n \in \Bbb N$, the following number is natural: $$\frac {(n!)!} {{n!}^{(n-1)!}}$$. I dont't know how to prove, as I tried to find a way including combinatorics.
0
votes
1answer
46 views

proof that if a|b and b|c then a|c [duplicate]

Just wanted some feed back on the following proof "if $a$ divides $b$ and $b$ divides $c$ then $a$ divides $c$" I came up with this: If $a|b$ then there exist some $x$ that $a * x = b$ and if ...
0
votes
4answers
70 views

Prove that if $n$ is divisible by a prime number $p$ then neither $n^2 +1$ nor $n^2 -1$ will be divisible by $p$.

I know this holds for $p=3$, but can it be generalized for any prime number? Can it be generalized further for any integer $p \in \Bbb N $ ?
1
vote
1answer
45 views

Probability that the a square-free number is divisible by a given prime number $p.$

Probability that the a square-free number $n$ is divisible by a given prime number $p$ is $1/(p+1).$ I know that $n$ is square-free and number of square-free integers up-to $x$ is $$ \approx x ...
0
votes
3answers
48 views

Find the $\gcd(pq, (p-1)(q-1))$ if $p$ and $q$ are prime. [closed]

Given prime numbers $p$, $q$, how do I prove that $\gcd(pq, (p-1)(q-1)) = p$, $q$ or $1$?
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 ...
11
votes
3answers
134 views

Doubt regarding divisibility of the expression: $1^{101}+2^{101} \cdot \cdot \cdot +2016^{101}$

In an interesting contest question I recently encountered, I chanced upon a question I couldn't solve. $$\sum^{2016}_{i=1}i^{101}$$ is divisible by: (a)2014 (b)2015 (c)2016 (d)2017 How would I ...
-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
98 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.
2
votes
2answers
52 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 ...
2
votes
1answer
37 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 ...
-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 ...
21
votes
1answer
637 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 ...
0
votes
2answers
62 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
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 ...
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$. ...
3
votes
4answers
65 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 ...
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 ...
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)$. ...
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 ...
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.
0
votes
0answers
32 views

Does there exist an integer $a(2<a<r)$ such that for all $n$ the alternative sum of $a^n$ is positive?

In arbitrary base r, Does there exist an integer a $(2<a<r)$, such that for any positive integer n,denote $$a^n=d_mr^m+d_{m-1}r^{m-1}+\cdots+d_1r+d_0,$$ then the alternative sum ...
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 ...
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.
5
votes
2answers
44 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
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? ...
0
votes
1answer
58 views

Prove that for any prime $p$ there exist natural numbers $a,b$ for which $ p$ divides $a^2+b^2+1$ [closed]

Prove that for each prime $p$ there exist natural numbers $a,b$ for which $p$ divides $a^2+b^2+1$
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 ...
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} + ...
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 ...
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
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
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
32 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$ ...
4
votes
3answers
96 views

$\frac{2abc}{(a+b-c)(b+c-a)(c+a-b)}$ a positive integer

Find all triplets $(a,b,c)$ of positive integers so that $\gcd(a,b,c)=1$ and $$ \frac{2abc}{(a+b-c)(b+c-a)(c+a-b)} $$ is a positive integer. What I've done: first I looked with Mathematica for ...
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
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 ...
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 ...
0
votes
4answers
59 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.
1
vote
1answer
18 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
52 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$. ...