Questions tagged [divisibility]
This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.
5,772
questions
0
votes
1
answer
52
views
Show: $\text{lcm}(a,a+p)=\text{lcm}(b,b+p), p \;\text{prime}\implies a=b$
(Romania Mathematical Olympiad). Let $a,b$ be positive integers such that exists a prime $p$ with the property $lcm(a,a+p)=lcm(b,b+p)$. Prove that $a=b$.
What I could do: WLOG $p|a, p \nmid b \...
3
votes
1
answer
89
views
n divides $m+1, m^m+1, m^{m^m}+1,...$
Prove that for each positive integer n, there is a positive integer m such that each term of the infinite sequence $m+1, m^m+1, m^{m^m}+1,...$ is divisible by n.
The only thing I could work out was ...
0
votes
0
answers
27
views
Prove that $a(a^{2}-1)$ is divisible by 6 [duplicate]
$a$ is a natural number that isn't equal to 0
My attempt:
$a(a^{2}-1)$ = $a(a-1)(a+1)$
There are 2 cases here:
If a = 2k:
We have $2k(2k+1)(2k+1)$ because $a-1$ and $a+1$ come before and after $a$ so ...
- 443
0
votes
0
answers
17
views
Division Algorithm (Euclid's division lemma) proof for integers as a corollary
I've seen different proofs of a fundamental result commonly referred to as Division Algorithm or Euclid's division lemma. I've read a lot of different proofs on it, but I find one thing confusing.
For ...
- 177
0
votes
0
answers
33
views
Prove that there exist $m,n\in\ \mathbb{N^*}$ such that $C$ divides $am+bn$
Let $C\geq10$ be an even integer and let $a,b\in\{1,2,3,....,C-1\}$
Prove that there exist $m,n\in\ \mathbb{N^*}(m,n\geq1)$ such that $C$ divides $am+bn$ such that $m+n\leq \frac{C}{2}+1$
My attempt:
...
- 874
0
votes
0
answers
42
views
Prove that if $n \mid a$ and $n \mid b$ then $n \mid (a+b)$ [duplicate]
As stated in the title, I need to prove that
if $n \mid a$ and $n \mid b$ then $n \mid (a+b)$.
So far this is what I have:
Assume that $n \mid a$ and $n \mid b$. Then there exists two integers $d$ ...
- 9
1
vote
0
answers
59
views
Characterization of primes of the form $n^n+1$ by using number-theoretic functions
It is known that there is a unsolved problem related to primes of the form $n^n+1$ as is expained in page 160 of [1] (see also page 156, and the OEIS page related to this integer sequence A121270). In ...
- 55
0
votes
0
answers
49
views
Is there a mistake in the second part of the workings of the proof?
For any n ∈ N, 64 is a factor of 32n+2 − 8n − 9.
For the n = 1 case, we see that 32n+2 − 8n − 9 = 34 − 8 − 9 = 81 − 17 = 64. Thus P(1) is true. Now suppose P(n) is true. Because 64 is the product of 4 ...
- 11
-1
votes
2
answers
55
views
Prove (by induction) For n $\in \mathbf{N}\ 13^{n+1} − 7^n$ is divisible by 6 [duplicate]
I started with:
$n=0: 13^{0+1} - 7^0 = 13-1 = 12$ divisible by 6.
$n=1: 13^{1+1} - 7^1 = 162 $ divisible by 6.
$13^{n+1} − 7^n = 6*k$ for any $k \in \mathbf{N}$
$n \longrightarrow n+1:$
\begin{align*}...
- 175
0
votes
0
answers
31
views
Does $\gcd(a, bc) = 1$ imply $\gcd(a, b) = 1$? [duplicate]
Assuming $a, b, c > 1$, then $(a, bc) = 1$ implies $b \not\mid a$, for if $b \mid a$, then we'd have $1 = (a, bc) \geq b > 1$ which is a contradiction. Likewise, $(a, bc) = 1$ also implies $c \...
- 1,059
4
votes
1
answer
282
views
Prove that there exist primes $p_{i}$ such that $\prod_{i=1}^{k}p_{i} \mid \sum_{i=1}^{k}(p_{i})^{a_{i}}$
If $k\geq 3$ is a given positive integer, prove that there exist prime numbers $p_{1}<p_{2}<\cdots<p_{k}$ and positive integers $a_{1},a_{2},\cdots,a_{k}$, such that
$$p_{1}p_{2}\cdots p_{k} ...
- 1
1
vote
1
answer
49
views
I want $a := mk^2 + mkn$ and $b := mkn + \frac{n^2m}{2}$ to be coprime. That, is I want $\gcd(a, b) = 1$. Which constraints on $m, k, n$ lead to this?
Let $m$, $k$, and $n$ be integers with $m \geq 2$ being even.
Let $a := mk^2 + mkn$ and $b := mkn + \frac{n^2m}{2}$.
How can I simplify $\gcd(a, b)$? Namely, how can I simplify
$$\gcd\left(mk^2 + mkn,\...
- 1,059
3
votes
2
answers
56
views
Find $100$th number $k$ such that there is no $n$ for which $n$! ends in $k$ zeroes.
$24! = 620,448,401,733,239,439,360,000$ ends in four zeroes, and $25! =
15,511,210,043,330,985,984,000,000$ ends in six zeroes. Thus, there is no integer
$n$ such that $n!$ ends in exactly five zeroes....
- 906
2
votes
1
answer
43
views
Divisibility of $\frac{3^n - 1}{2}$ by $2^k$ [duplicate]
I would like to find the greatest k such that $p=\frac{3^n - 1}{2}$ is divisible by $2^k$.
Since $p$ is the repunit number in base 3 it is already clear that if $n$ is even, $p$ would be divisible by ...
- 75
2
votes
0
answers
73
views
Are there infinite many primes $\ p\ $ that cannot divide $\ 3^n+5^n+7^n\ $?
Let $\ M\ $ be the set of the prime numbers $\ p\ $ such that $\ p\nmid 3^n+5^n+7^n\ $ for every positive integer $\ n\ $ , in short the set of the prime numbers that cannot divide $\ 3^n+5^n+7^n\ $.
...
- 78.4k
0
votes
1
answer
43
views
When is $n = \frac{a_{1}x^{2} + a_{2}x + a_{3}}{a_{4}x + a_{5}}$ an integer where $a_{i}$ are incredibly large integers? [closed]
I have the equation with the following form:
$$n = \frac{a_{1}x^{2} + a_{2}x + a_{3}}{a_{4}x + a_{5}}$$
Where $a_{i}$ are incredibly large (e.g 1000 digits) but unrelated (not part of sequence or ...
- 31
2
votes
2
answers
82
views
Finding the maximum $k$ such that $(7!)!$ is divisible by $(7!)^{k!}\cdot(6!)!$
If $(7!)!$ is divisible by $(7!)^{k!}\cdot(6!)!$, then what is the maximum value of $k$?
At first glance I couldnt think of anything except Legendre's formula for calculating powers of a prime in a ...
- 149
20
votes
3
answers
638
views
Is $\frac{3^n+5^n+7^n}{15}$ only prime if $n$ is prime?
Let $f(n)=3^n+5^n+7^n$
It is easy to show that $\ 15\mid f(n)\ $ if and only if $\ n\ $ is odd.
I searched for prime numbers of the form $g(n):=\frac{3^n+5^n+7^n}{15}$ with odd $n$ and found the ...
- 78.4k
1
vote
1
answer
36
views
How to understand the fast divisibility check for a double-width dividend?
I found this algorithm from the GNU factor utility.
Given a double width dividend $n=n_1B + n_0$ and a single width odd divisor $d$, where $n_1, n_0, d < B=2^w, 2\nmid d$. Then with the precomputed ...
- 13
3
votes
1
answer
78
views
Prove that if $a \mid c$ and $b \mid c$, then $ab \mid c^2$ [duplicate]
I am trying to solve this problem, but I am unsure if my proof if sufficient or not. Anyways, here is what I have tried:
So, by using the definition of "divides" I get:
(i): If $a \mid c$, ...
- 87
1
vote
2
answers
77
views
Prove that $p_1\cdots p_k - 1$ and $p_1\cdots p_l - 1$ are coprime and that $p_1\cdots p_k + 1$ and $p_1\cdots p_l+1$ are coprime.
Let $p_n$ denote the nth prime and suppose $l\neq k$. Prove or disprove that $p_1\cdots p_k - 1$ and $p_1\cdots p_l - 1$ are coprime. Prove or disprove that $p_1\cdots p_k + 1$ and $p_1\cdots p_l+1$ ...
- 893
-1
votes
1
answer
28
views
Is there a simple test for divisibility by seventeen in base-twelve? [duplicate]
I am investigating math in the dozenal (a.k.a. duodecimal, base-twelve) system. As part of this, I am compiling a list of tests for divisibility. (All numbers in this post are dozenal, not decimal, ...
- 751
1
vote
0
answers
56
views
On Carmichael function and aliquot parts of odd perfect numbers
We denote as $N$ an odd perfect number, and $d\mid N$ one of its divisors. We denote the Carmichael function as $\lambda(x)$, Wikipedia has the article Carmichael function dedicated to this number ...
- 55
4
votes
2
answers
228
views
Is there a simple test for divisibility by sixteen in base-twelve?
I am investigating math in the dozenal (a.k.a. duodecimal, base-twelve) system. As part of this, I am compiling a list of tests for divisibility. (All numbers in this post are dozenal, not decimal, ...
- 751
0
votes
0
answers
54
views
Does $I = \gcd(n,\sigma(n^2)) = (\frac{n}{\sigma(q^k)/2})\cdot\gcd(\sigma(q^k)/2,n)$ imply that $\sigma(q^k)/2 \mid n$ holds?
Let $N = q^k n^2$ be an odd perfect number with special prime $q$ satisfying $q \equiv k \equiv 1 \pmod 4$ and $\gcd(q,n)=1$.
Define the GCDs:
$$G = \gcd\bigg(\sigma(q^k),\sigma(n^2)\bigg)$$
$$H = \...
- 10.2k
-1
votes
2
answers
67
views
How to understand special prime factorization method
Normally when we want to find the Prime Factorization of a number, we will keep dividing that number by the smallest prime number (2), until it can't be divided then we move on to the next prime ...
1
vote
0
answers
55
views
Show that for any integer $n$, $n^2+2n+11$ is not a multiple of $121$. [duplicate]
Show that for any integer $n$, $n^2+2n+11$ is not a multiple of $121$.
Attempt:
Suppose for contradiction that there exists an integer $n$ such that $n^2+2n+11$ is a multiple of $121$. Since $121=11^2$...
- 620
1
vote
0
answers
12
views
How to prove concerning points on a hemisphere? [duplicate]
The questions in my textbook asks:
"Given a sphere $S$, a great circle of $S$ is the intersection of $S$ with a plane through its center. Every great circle divides $S$ into two parts. A ...
- 115
0
votes
0
answers
51
views
Is my proof for $m|a\land m|b\Longrightarrow m|\alpha a+\beta b$ correct? [duplicate]
I just did a proof for $m\mid a\ \land m\mid b\Longrightarrow m\mid (\alpha a+\beta b)$ but it feels a bit weak. Can someone please check it and let me know if it is complete? Thank you in advance.
\...
- 19
3
votes
3
answers
80
views
Find all integers $n$ such that $\frac{3n^2+4n+5}{2n+1}$ is an integer.
Find all integers $n$ such that $\frac{3n^2+4n+5}{2n+1}$ is an integer.
Attempt:
We have
\begin{equation*}
\frac{3n^2+4n+5}{2n+1} = \frac{4n^2+4n+1 - (n^2-4)}{2n+1} = 2n+1 - \frac{n^2-4}{2n+1}.
\end{...
- 620
9
votes
0
answers
222
views
Do prime of the form $4k+1$ ever lead the greatest prime factor race?
Analogous to Chebyshev's race between primes, I examined the race between primes in the greatest prime factors, GPF, of natural numbers. Similar to the regular prime race, in the GPF race, the ...
- 15.5k
1
vote
0
answers
31
views
On the equation $\sigma\left(\square\right)=\text{prime}$: propositions that can be potentially interesting or reference request
For integers $A,B\geq 1$ we define the difference $\sigma(A)\sigma(B)-\sigma(AB)$, denoting it as $[A,B]$, where $\sigma(n)=\sum_{1\leq d\mid n}d$ denotes the sum of divisors function. It is possible ...
- 55
0
votes
1
answer
79
views
Let $H\le G, g\in G$ with order $n$, and $gH\in G / H$ with order $d$. Show $d$ divides $n$.
Let $H$ be a normal subgroup of $G$. Now, $g\in G$ has order $n$ and $gH\in G / H$ has order $d$. Show that $d$ divides $n$.
So, $H\le G$, $|g|=n$, and $|gH|=d$
If $d\mid n$, then $dt=n$, some $t\in \...
- 409
0
votes
2
answers
46
views
For fixed $a\ge 2$, find $n$ such that $a^2+a+1$ divides $a^{2n}+a^n+1$
For fixed $a\ge 2$, find $n$ such that $a^2+a+1$ divides $a^{2n}+a^n+1$.
If the statement is about polynomials (replacing $a$ by an indeterminate $x$), then I would argue by remarking that roots of $x^...
- 490
1
vote
1
answer
92
views
Show that the equation $x^2+4 = 3(y-1)$ has no integer solutions using the division algorithm.
Please don't mark this as duplicate as questions similar to this one all have answers using modular arithmetic and I'm looking for a solution using the Division Algorithm.
My thinking:
$x^2+4 = 3(y-1)$...
- 387
3
votes
2
answers
159
views
How many more odd divisors are there than even divisors?
Let $f(k)$ be the number of odd divisors of $k$ and $g(k)$ be the number of even divisors. Define $F(n) = \sum_{k \le n} f(k)$ and $G(n) = \sum_{k \le n} g(k)$. Thus $F(n)$ and $G(n)$ are the total ...
- 15.5k
1
vote
0
answers
125
views
Replace x with x + divisor of x, starting from 1, to reach target number
How can I find the minimum number of steps to go from initial number i = 1 to a target number n using the following transformation: replace i with i + d, where d divides i.
For example, for n = 7, the ...
- 11
0
votes
0
answers
26
views
Number theory(elementry) [duplicate]
How can we prove that $10^{10^{10^n}} +10^{ 10^n} + 10^n-1$ is not prime for all positive intigers $n$?
- 1
21
votes
3
answers
2k
views
Why do all "divisibility tricks" seem to use linear combinations, and are there any that don't?
When I say "divisibility trick" I mean "a recursive algorithm designed to show that, after multiple iterations, if the final output is a multiple of the desired number, then the ...
- 1,137
-2
votes
3
answers
99
views
If $j$ and $k \in \mathbb{N}$, and $37j = 12k$, prove $j + k$ is divisible by $7$ [duplicate]
My thinking:
$37j = 12k \rightarrow \:j+k=\frac{49j}{12}$
$\frac{49j}{12}$ = $7\left(\frac{7j}{12}\right)$
Here's where I'm stuck. How do I show that $\left(\frac{7j}{12}\right) \in \mathbb{N}$
Thank ...
- 387
1
vote
1
answer
83
views
Calculate $\gcd(a^2b^2, a^2 + ab + b^2)$ [duplicate]
Given $\gcd(a, b) = 1$, calculate $d =\gcd(a^2b^2, a^2 + ab + b^2)$ in terms of $a$ and $b$.
I have tried some manipulations of the terms arriving to some expressions such as that $d$ divides $a^4 + b^...
- 129
-1
votes
1
answer
55
views
Determine the polynomials $P \in \mathbb{R}[X] $ such that : $X^n$ divides $X + 1 − P^2$.
please an idea to start the following exercise:
Determine the polynomials $P \in \mathbb{R}[X] $ such that : $X^n$ divides $X + 1 − P^2$.
Thank you in advance
- 39
2
votes
1
answer
30
views
Finding monic integer polynomial of lowest degree with all outputs multiple of an integer
I was working with a student on the following problem (source unknown)
Let $f(n)$ be the minimum degree of a monic polynomial $p$ such that for all integers $m$, $p(m)$ is a multiple of $n$. Evaluate ...
- 13.4k
9
votes
0
answers
81
views
Divisibility and Lagrange Theorem
I came across the following question from math olympiad:
For $n\in \mathbb{Z}^+$, prove that $$n!\mid\prod_{k=1}^n(2^n-2^{k-1}).$$
While I can solve it using elementary number theory, I notice that $...
- 1,447
1
vote
1
answer
84
views
2022 Mathleague Target Round question 8 [closed]
I participated in the 2022 Mathleague Middle school competition, and I was presented the following problem as the last question on the Target Round: "If $x$ is equal to the estimate of $\frac{n}{...
- 41
0
votes
1
answer
34
views
Irreducible Polynomial in $\mathbb{F}_p (T) [x]$ [duplicate]
Let p be prime, and $K = {\bf F}_p (T)$ an extension of ${\bf F}_p$. How can i prove that the polynomial $x^p - T$ is irreducible in $K[x]$
- 29
1
vote
1
answer
36
views
Is division by a null sedenion a valid operation?
So octonion set provides the largest normed division algebra, and starting with sedenions, Cayley-Dickson construction provides algebras with zero divisors.
From what I understand, it means there are ...
- 113
0
votes
1
answer
54
views
Two basic questions
Here are two basic questions to which I currently do not know the answer:
(1) If $a > 0$ and $b$ are integers (where $b$ is negative), then if there exists a (necessarily) negative integer $c$ ...
- 10.2k
-1
votes
1
answer
61
views
$\frac{P(x)}{x^2+3}$ is $2x+5$, find the remainder of $\frac{[P(x)]^2}{x^2+3}$
The remainder of $\frac{P(x)}{x^2+3}$ is $2x+5$
$$$$
Find the remainder of
$$\frac{[P(x)]^2}{x^2+3}$$
The approach I have attempted for this exercise is to write $P(x)=(x^2+3)Q_1(x)+2x+5 ...(1)$ and ...
- 1
0
votes
1
answer
92
views
how to find the number of integers between two numbers inclusive that are divisible by any of the two numbers X or Y. [closed]
You are given 4 integers X, Y, L, R. You need to find the number of integers between L and R inclusive that is divisible by any of the two numbers X or Y.
How to find the answer without trying all ...
- 87