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
0answers
14 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
59 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 ...
1
vote
6answers
105 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 ...
3
votes
1answer
20 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 ...
0
votes
2answers
65 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}$, $...
0
votes
1answer
13 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
450 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$...
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 ...
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 ...
3
votes
1answer
35 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 ...
2
votes
2answers
45 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 ...
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
62 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
4answers
42 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} = \...
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)$.
-2
votes
1answer
48 views

Is it proper to say that zero divided by an integer $x$ has a remainder of $x$?

Is, for instance, $$\frac{0}{3} = 0$$ with a remainder of $3$? Thank you (:
1
vote
2answers
39 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 ...
2
votes
8answers
196 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 ...
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 ...
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 ...
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 $...
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 ...
1
vote
3answers
77 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?
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?
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(...
1
vote
4answers
73 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\...
2
votes
6answers
117 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)=(...
-4
votes
6answers
136 views

Smallest number evenly divisible by numbers 1 to 500 [closed]

How can I find smallest number evenly divisible by numbers 1 to 500?
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
5answers
90 views

Prove by induction that $3^{2n+3}+40n-27$ is divisible by 64 for all n in natural numbers

I cannot complete the third step of induction for this one. The assumption is $3^{2n+3}+40n-27=64k$, and when substituting for $n+1$ I obtain $3^{2n+5}+40n+13=64k$. I've tried factoring the expression,...
0
votes
3answers
51 views

Show that for all $a\in\mathbb{N}$, there exists $b\in\mathbb{N}$ and square-free integer $c$ such that $\sqrt{a}=b\sqrt{c}$.

I'm having some difficulties continuing this problem. I get that $b^2\mid a$ and $c\mid a$ but I am not sure where to go from there.
3
votes
2answers
16 views

Prove that $a \mid k$ if $a \mid k·c$, $a \mid k·b$ and $gcd(c,b)=1$ for all $a,b,c,k \in \mathbb{Z}$ [closed]

Let $a,b,c,k \in \mathbb{Z}$ and $a \mid k·c$, $a \mid k·b$ and $gcd(c,b)=1$. Prove that $a \mid k$.
-1
votes
3answers
82 views

How many numbers are there in range 1 to 1000 which contains digits 2 and 3 and divisible 2 and 3?

How many numbers are there in range 1 to 1000 which contains digits 2 and 3 and divisible 2 and 3? I know the answer to find count of numbers in range 1 to 1000 which are divisble by 2 and 3. But the ...
1
vote
2answers
63 views

Numbers $a$ such that if $a \mid b^2$ then $a \mid b$

I want to describe the set of numbers $a$ such that if $a \mid b^2$ then $a | b$ for all positive integers b using the prime factorizations of $a$ and $b$. What would be a good way to approach this ...
5
votes
3answers
120 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 $...
2
votes
2answers
64 views

Suppose $ab\equiv 0 \pmod{n}$, and that $a$ and $b$ are positive integers both less than $n$. Does it follow that either $a | n$ or $b | n$?

Suppose $ab\equiv 0 \pmod{n}$, and that $a$ and $b$ are positive integers both less than $n$. Does it follow that either $a | n$ or $b | n$? If it does follow, give a proof. If it doesn’t, then give ...
-3
votes
4answers
92 views

Prove that if $n/m$ is even then $\gcd(2^m+1,2^n+1)=1$ [closed]

Let $m,n\in \mathbb N$ , such that $m\mid n$. show that if $\frac{n}{m}$ is even then $\gcd(2^m+1,2^n+1)=1$ My attempt: I took $n=14$ and $m=7$ $$\gcd(2^n+1,2^m+1)=\gcd(2^{14}+1,2^{7}+1)=\gcd(...
0
votes
0answers
15 views

Decomposition of an element of the convex hull

Let natural numbers $ 2 \le c_m \mid c_{m-1} \mid \ldots \mid c_1 $ and $ C \in \mathbb{N} $ with $ C\ge c_1 $ be given, and define $ P:=\operatorname{conv}\left\lbrace x \in \mathbb{Z}^m_{\ge 0} \, \...
1
vote
1answer
101 views

How to prove $\frac{(2n)!(2m)!}{n!m!(n+m)!}$ is an integer by strictly using my method?

I have to prove that $$\frac{(2n)!(2m)!}{n!m!(n+m)!}$$ is always an integer. I already have seen the same question here-Prove that for all non-negative integers $m,n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}...
0
votes
1answer
28 views

Set of “perfect” Numbers in quantor logic

Write $D=\{6,28\}$ as the set of perfect numbers which are bigger then 2 and smaller then 30. $D=\{x\in\mathbb{N}:(2<x<30)\wedge (d_{1,2,...,i}\in(\{d\in\mathbb{N}:d|x\}\backslash\{x\}):d_1+d_2+...
2
votes
1answer
48 views

Does $n\mid(a^n-b^n)$ imply $n\mid(a^n-b^n)/(a-b)$? [duplicate]

Finding my previous question quite naive, I improve my question: Given that $n,a,b \in \mathbb{N}$ and $n\mid(a^n-b^n)$ , can we prove or disprove $n\mid(a^n-b^n)/(a-b)$ ?
1
vote
2answers
65 views

Does $n\mid(a^n-b^n)$ imply $n\mid(a-b)$?

Given that $n,a,b \in \mathbb{N}$ and $n\mid(a^n-b^n)$ , can we prove or disprove $n\mid(a-b)$ ? Using Fermat's little theorem, we can prove the case when n is a prime number. What about the case ...
6
votes
1answer
68 views

Prove the sum of squares of 3 rationals cannot be 7

Prove there isn't $r_1, r_2,r_3 \in \mathbb{Q}$ so that ${r_1}^2 + {r_2}^2 + {r_3}^2=7 \tag1$ From (1) we get $a^2 + b^2 + c^2=7n^2 \tag2$ where $a,b,c,n \in \mathbb{N}$. I have tried playing ...
0
votes
1answer
13 views

Existence of a Repeating Divisor

I have $n$ integers $a_1, a_2, a_3, .., a_n$ let $X = a_1*a_2*a_3*...*a_n$. I want to know a single integer $F$ such that $F^2$ divides $X$. It is told that there will be atleast one such $X$ and ...
5
votes
6answers
118 views

Find a six digit integer [closed]

Find an integer with six different digits such that the six digit integer is divisible by each of its digits. For example, find ABCDEF such that A, B, C, D, E and F all can divide the number ABCDEF. ...
1
vote
1answer
39 views

Unable to understand why gcd(bt+r,b)=gcd(b,r) [duplicate]

I am trying to understand greatest common divisor so If a=bt+r for integers t & r then why gcd(a,b)=gcd(b,r).I am unable to understand it.
4
votes
2answers
58 views

Let $P(x)=ax^{2014}-bx^{2015}+1$ and $Q(x)=x^2-2x+1$ such that $Q(x)|P(x)$, find $a+b$

Let $P(x)=ax^{2014}-bx^{2015}+1$ and $Q(x)=x^2-2x+1$ be the polynomials where $a$ and $b$ are real numbers. If polynomial $P$ is divisible by $Q$, what is the value of $a+b$. This is what I have ...
2
votes
5answers
67 views

Prove that $\gcd(2^{a}+1,2^{\gcd(a,b)}-1)=1$

Let $a$ and $b$ be two odd positive integers. Prove that $\gcd(2^{a}+1,2^{\gcd(a,b)}-1)=1$. I tried rewriting it to get $\gcd(2^{2k+1}+1,2^{\gcd(2k+1,2n+1)}-1)$, but I didn't see how this helps.