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

learn more… | top users | synonyms

11
votes
1answer
196 views

Are there infinitely many pairs of primes where each divides one more than the square of the other?

I have the following question on number theory that is eating my head. Are there infinitely many primes $p,q$ such that $p | (q^2 + 1)$ and $q | (p^2 + 1)$? I can see $13,5$ and $2,5$ has the ...
0
votes
0answers
15 views

Prove that the product of $n$ consecutive integers is divisible by $n!$ [duplicate]

Problem : Prove that the product of $n$ consectutive integers is divisible by $n!$. $n!\mid a(a+1)(a+2)...(a+n-1)$
2
votes
3answers
61 views

Remainder of $2^{125}/13$

Remainder of $2^{125}/13$ According to Microsoft Excel, the answer is 6 I was expecting a shorter pattern with remainders such as 3,6,12,... How to go about doing this simply? I thought of ...
2
votes
3answers
107 views

For what powers $k$ is the polynomial $n^k-1$ divisible by $(n-1)^2$? [closed]

How do you prove this? $$\left(n-1\right)^2\mid\left(n^k-1\right)\Longleftrightarrow\left(n-1\right)\mid k$$
1
vote
6answers
119 views

Why is $10^k - 1$ divisible by $9$?

I know it is obvious that $10^k-1$ will always be divisible by $9$ for some integer $k$, but I am curious how to actually prove this. $$10^k - 1 \equiv 0 \bmod 9$$ $$10^k \equiv 1 \bmod 9$$ ... and ...
0
votes
2answers
66 views

Determine all $n$-digit numbers that are divisible by the cyclic permutations of its digits

Given an integer $n \geq 2$, determine all $n$-digit numbers $M_0 = \overline{a_1a_2 \ldots a_n}$ $(a_i \neq 0, i = 1,2,\ldots,n)$ divisible by the numbers $M_1 = \overline{a_2a_3 \ldots a_na_1}$, $...
3
votes
1answer
21 views

Maximum length of a string that has no substring divisible by a prime number $p$ is $p-1$?

What is the maximum length of a string of nonzero digits that has no substring that is divisible by a given prime number? I want to find a string of length n which has no substring divisible by the ...
10
votes
4answers
3k views

Fibonacci sequence divisible by 7?

Make and prove a conjecture about when the Fibonacci sequence, $F_n$, is divisible by $7$. I've realized it's when $n$ is a multiple of $8$. I just don't know how to go about proving it.
0
votes
1answer
15 views

Divide items with integer ID-s into N equal groups, based on ID-s

I have unknown number of items, each having ID (consecutive integer numbers), ie. 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15... I want to split above items into as ...
3
votes
4answers
453 views

Discrete Math Understanding a proof involving the definition of divisibility

In this first course on discrete mathematics, the instructor provided this following solution to a question. The question was asked us to prove the following (the solution is provided as well): My ...
8
votes
0answers
95 views

How many ways can I arrange the numbers $1$ to $N$ with this divisibility condition?

For the numbers $1, \ldots, N$, how many ways can I arrange them such that either: The number at $i$ is evenly divisible by $i$, or $i$ is evenly divisible by the number at $i$. Example: for N = 2$...
2
votes
8answers
200 views

Showing that $2^6$ divides $3^{2264}-3^{104}$

Show that $3^{2264}-3^{104}$ is divisible by $2^6$. My attempt: Let $n=2263$. Since $a^{\phi(n)}\equiv 1 \pmod n$ and $$\phi(n)=(31-1)(73-1)=2264 -104$$ we conclude that $3^{2264}-3^{104}$ is ...
0
votes
1answer
18 views

Discrete Math Proof: Divisibility equivalence

For all integers $a$, $b$, $d$, if $d$ divides $a$, and $d$ divides $b$, then $d$ divides $(3a+2b)$ and $d$ divides $(2a+b)$. Prove the statement. What Assumptions do I need to make at the beginning ...
5
votes
3answers
121 views

Find $n$ with $100<n<2000$ such that $2^n+2$ is divisible by $n$?

Find a number $n$ with $100<n<2000$ such that $2^n+2$ is divisible by $n$ ? Its can easily be seen that $n=6$ is possible case but it does not satisfy the main constraint of being greater than $...
1
vote
1answer
30 views

If I know N%m , can I compute (N/2)%m? If yes, then how?

This question arrised when I was solving a computer science problem. I don't know the value of N, as N may be very large, but instead I know the value of $N \mod m$. Assume N is divisible by 2. How ...
2
votes
5answers
152 views

How to prove that $x^a-1|x^b-1 \Longleftrightarrow a|b$.

Prove that $x^a-1|x^b-1 \Longleftrightarrow a|b$, where $x \ge 2$ and $a,b,x \in \Bbb Z$. I've tried the following in attempting to solve this: $$a|b \rightarrow aq=b \rightarrow x^{aq}=x^b \...
1
vote
1answer
47 views

Conjecture about divisibility: if $d \mid n$, then there exists $r,s$ such that $n=r+s$ and $d = \gcd(r,s)$

Given $n\in\mathbb Z^+$. If $d<n>1$ and $d\mid n$ it exists $r,s\in \mathbb Z^+$ such that $n=r+s$ and $d=\gcd(r,s)$.
3
votes
1answer
36 views

Divisible to the right in circle

Numbers $1,2,\dots,300$ are placed in a circle in some order. At most how many numbers can be divisible by the number to its right? One way (probably optimal) is to place numbers so that $m$ is ...
6
votes
1answer
81 views

Sequences where each number is a divisor of one less than the next

Let $N,k$ be fixed. Call a sequence of positive integers $a_1,a_2,\dots,a_k$ good if for each $i$, $a_i$ is a divisor of $a_{i-1}-1$. Consider the set $$S = \{x : \text{$x$ occurs in some good ...
5
votes
3answers
179 views

Does $\gcd(a,bc)$ divides $\gcd(a, b)\gcd(a, c)$?

I want to prove that $\gcd(a,bc)$ divides $\gcd(a,b)\gcd(a,c)$ but I can't succeed. I tried to go with $\gcd(a,b) = sa+tb$ and it didn't work, tried to use the fact that $\gcd(a,b)$ and $\gcd (a,c)$ ...
2
votes
1answer
63 views

If $q\mid 2^p + 3^p$ then $q \gt p$

Let $p, q$ positive prime numbers, $q > 5$. Prove that if $q \mid \left(2^{p} + 3^{p}\right)$ then $q > p$. First, it's clear that $p \ne q$ because, using Fermat's little theorem, $2^p = ...
2
votes
2answers
46 views

An unexplained condition on $a$ in a proof on the primes?

Lemma A positive integer $n$ is a prime if $(n,p) = 1$ for every prime integer $p \leq \sqrt{n}$ Proof in my text Let $(n,p) = 1$ for every prime $p \leq \sqrt{n} \:$. Suppose $n$ is not a ...
2
votes
4answers
43 views

Proving that these terms have no common factors

If $m = a_1x + b_1y$ , $n = a_2x + b_2y$ , $a_1b_2 - a_2b_1 = 1$ then prove that $\gcd (m,n) = \gcd (x, y)$ My attempt Let $c = \gcd (x,y)$ and $d = \gcd (m,n)$ then $c \mid d$ $\frac{d}{c} = \...
0
votes
2answers
63 views

How can I prove $1^{n+2} + 2^{n+2} + 3^{n+2} + 4^{n+2}$ is divisible by $10$ for any odd $n$?

Assuming this is true: $1^n+2^n+3^n+4^n$ divisible by $10$ for any odd $n$ ($n$ is natural) How can I prove that for $n+2$: $1^{n+2} + 2^{n+2} + 3^{n+2} + 4^{n+2}$ Is divisible by 10 as well ? ...
2
votes
1answer
201 views

The greatest common divisor is the smallest positive linear combination

How to prove the following theorems about gcd? Theorem 1: Let $a$ and $b$ be nonzero integers. Then the smallest positive linear combination of $a$ and $b$ is a common divisor of $a$ and $b$. ...
1
vote
2answers
290 views

Greatest common divisor is the smallest positive number that can be written as $sa+tb$

We know that $d = \gcd(a, b)$ can be written as $sa + tb$, where $s, t \in \mathbb{Z}$. Apparently, $d$ is the smallest positive number that can be written in this form. Why is this so?
2
votes
0answers
43 views

Can an odd perfect number be divisible by either $2049$ or $2051$?

Can an odd perfect number be divisible by either $2049$ or $2051$? Note that $2049 = 3 \cdot {683}$, and that $2051 = 7 \cdot {293}$. Added July 15 2016 It is known that an odd perfect number ...
16
votes
5answers
992 views

Divisibility for 7

I have seen other criteria for divisibility by 7. Criterion described below present in the book Handbook of Mathematics for IN Bronshtein (p. 323) is interesting, but could not prove it. Let $n = (...
0
votes
6answers
78 views

Prove that $3$ divides $2^{2^n}$ − 1 for all integers $n ≥ 1$ [duplicate]

My answer: if $3|2^{2^n}-1$ then there must be an integer $j$ such that $3j=2^{2^n}-1$. then I needed help to continue if I am correct?
2
votes
3answers
1k views

how $1/0.5$ is equal to $2$?

My question is how $1/0.5$ is equal to $2$. I am not asking the mathematical justification that $1/0.5=10/5=2$. I know all this. I just want to know how it is two... a lay man justification. ...
10
votes
5answers
473 views

Show that $\gcd\left(\frac{a^n-b^n}{a-b},a-b\right)=\gcd(n d^{n-1},a-b)$

How to show that $$ \gcd\bigg( {a^n-b^n \over a-b} ,a-b\bigg )=\gcd(n d^{n-1},a-b ) $$ $a,b\in \mathbb Z$ where $d=\gcd(a,b)$? Note $\ $ Some of the answers below were merged from this ...
-2
votes
1answer
48 views
1
vote
2answers
40 views

Can it proved that the GCD does not divide the integer coefficients in the linear form of the GCD?

Let $d = (a,b)$ then $d = ax +by$ for some $x,y \in \mathbb{Z}$ I want to prove that $d \nmid x,y$. Motivation I'm trying to solve the following problem: If $a$ is prime to $b$ and $y$, $b$ is ...
4
votes
1answer
63 views

If $ a_n$ is increasingly divisible by $2$ and not a multiple of $10$ then the sum of its digits goes to infinity

Let $(a_n)_{n \geq 0}$ be a sequence of positive integers not divisible by 10 such that the number of factors 2 in $a_n$ tends to infinity for $n \to \infty$. Prove that the sum of the digits of an in ...
2
votes
8answers
235 views

Prove that $4$ divides $3^{2m+1} - 3$

Prove that $4$ divides $3^{2m+1} - 3$. By plugging in numbers I can see this is true, but I can't figure out a way to prove this, I was thinking maybe proving first that it is divisible by $2$, and ...
0
votes
2answers
63 views

How do I show $1$ is not a trivial odd perfect number?

This question related to my this question in MO ,some comments stated that the integer $1$ is trivial answer for this question ,but here i'm very confused when we say that the sum divisors of $1$ is $...
11
votes
2answers
548 views

If $R$ is a commutative ring with identity, and $a, b\in R$ are divisible by each other, is it true that they must be associates?

My problem is: If $R$ is a commutative ring with identity, and $a, b\in R$ are divisible by each other, is it true that they must be associates? Here, $a$ being divisible by $b$ means there ...
1
vote
0answers
15 views

If $N \neq p^k$, $(\sigma(N) - N) \mid (N - 1)$, and $3 \mid (N - 1)$, does it follow that $\nu_{3}(\sigma(N) - N) \neq \nu_{3}(N - 1)$?

(Note: This has been cross-posted from MO.) The title says it all. Let $\sigma=\sigma_{1}$ be the classical sum-of-divisors function. Here is my question: Original Problem (Note: This has been ...
1
vote
3answers
36 views

Is this enough to prove that the GCD is larger?

Prove that $(a+b, a-b) \geq (a, b)$ My attempt Let $(a+b, a-b) = d$ and $(a, b) = c$. Since $c \mid a,b$ $c$ is also a factor of $a+b$ and $a-b$. Thus $c \leq d$. Is this enough as a proof? It ...
1
vote
3answers
78 views

Is it possible that $n^2+1$ has some divisor of the form $4k+3$?

Given an integer $n$, we are asked to investigate about the existence of integer divisors of $n^2+1$ of the form $4k+3$. Can you provide some insights about it?
2
votes
1answer
36 views

$a_i \mid r $ implies that $r = 0$ if $0 \leq r < a$?

If $x$ is any common multiple of $a_1, a_2 \cdots a_n$ all $\neq 0$ then prove that $[a_1, a_2,\ldots,a_n]$ divides $x$. Note, $[a_1, a_2,\ldots,a_n]$ is LCM. The solution provided in my text: Let $...
3
votes
3answers
124 views

If $\gcd(a,c)=1=\gcd(b,c)$, then $\gcd(ab,c)=1$

As stated in the title, the problem to prove is Let $a,b,c \in \mathbb{Z}$. If $\gcd(a,c)=1=\gcd(b,c)$, then $\gcd(ab,c)=1$. I think I've proved it, but I would like a second opinion. Here goes:...
2
votes
3answers
87 views

Show that among every consecutive 5 integers one is coprime to the others

Show that among every consecutive 5 integers one is coprime to the others I considered these 5 numbers as: $5k,5k+1,5k+2,5k+3,5k+4$ It's seen that for example $5k+1$ is coprime to $5k$ and $5k+2$,now ...
1
vote
3answers
85 views

Proof involving gcd and congruence.

So here is the statement: $m \in \mathbb{N} $ and $ a,b \in \mathbb{Z}$. Prove that $\gcd (a,m)=\gcd(b,m)$ iff there are solutions to the linear congruences $ax\equiv b\,(\text{mod}\,\, m)$ and $by\...
1
vote
2answers
34 views

Prove that if $d\mid\gcd(a,b)$, then $d\mid a$ and $d\mid b$.

Prove that if $d\mid\gcd(a,b)$, then $d\mid a$ and $d\mid b$. I saw this used in proving another theorem but it was not proved. Does anyone know how to prove it?
2
votes
6answers
118 views

Find all the numbers $n$ such that $\frac{12n-6}{10n-3}$ can't be reduced.

Find all the numbers $n$ such that $\frac{12n-6}{10n-3}$ can't be reduced. Attempt: It can't be reduced when $\gcd(12n-6,10n-3)=1$ Here $(a,b)$ denotes $\gcd(a,b)$ $$(12n-6,10n-3)=(12n-6,2n-3)=(...
3
votes
3answers
138 views

Divisor in $\mathbb{C}[X]$ $\implies$ divisor in $\mathbb{R}[X]$?

let $P \in \mathbb{R}[X]$ be a real polynomial divisible by a polynomial $Q \in \mathbb{R}[X]$ in $\mathbb{C}[X]$. How can I easily show that $P$ is also divisible by $Q$ in $\mathbb{R}[X]$? A simple ...
8
votes
4answers
250 views

Is $77!$ divisible by $77^7$?

Can $77!$ be divided by $77^7$? Attempt: Yes, because $77=11\times 7$ and $77^7=11^7\times 7^7$ so all I need is that the prime factorization of $77!$ contains $\color{green}{11^7}\times\color{blue}...
1
vote
4answers
74 views

Find all the numbers $n$ such that $\frac{4n-5}{60-12n}$ can't be reduced.

Find all the numbers $n$ such that $\frac{4n-5}{60-12n}$ can't be reduced. Attempt: $$\gcd(4n-5,60-12n)=(4n-5,-8n+55)=(4n-5,-4n+50)=(4n-5,45)$$ $$n=1: (4-5,45)=1\quad \checkmark\\ n=2: (3,45)=3\...
4
votes
2answers
58 views

Find all the numbers $n$ such that $\frac{6n-8}{2n-5}$ can't be reduced. [duplicate]

Find all the numbers $n$ such that $\frac{6n-8}{2n-5}$ can't be reduced. Attempt: It can't be reduced when $\gcd(6n-8,2n-5)=\color{red}1$ $$1 = \gcd(6n-8,2n-5)=\gcd(4n-3,2n-5)=\gcd(2n+2,2n-5)=\gcd(...