Questions tagged [divisibility]

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

Filter by
Sorted by
Tagged with
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 \...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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: ...
user avatar
  • 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$ ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
-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*}...
user avatar
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 \...
user avatar
  • 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} ...
user avatar
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,\...
user avatar
  • 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....
user avatar
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 ...
user avatar
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\ $. ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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$, ...
user avatar
  • 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$ ...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
  • 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 = \...
user avatar
-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 ...
user avatar
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$...
user avatar
  • 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 ...
user avatar
  • 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. \...
user avatar
  • 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{...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 \...
user avatar
  • 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^...
user avatar
  • 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)$...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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$?
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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^...
user avatar
  • 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
user avatar
  • 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 ...
user avatar
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 $...
user avatar
  • 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}{...
user avatar
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]$
user avatar
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 ...
user avatar
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$ ...
user avatar
-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 ...
user avatar
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 ...
user avatar

1
2 3 4 5
116