Questions tagged [divisibility]
This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.
4,294 questions
2
votes
1answer
59 views
Divisibility of $x^2+y^2$ by prime $p$
I've read the following fact on my number theory textbook, there's no proof on the book of such result, I tried working it out on my own but I'm kinda lost, the lemma is the following:
Given two ...
-1
votes
0answers
9 views
How can the facial thirds be measured without reference points? [on hold]
So I have an interesting question regarding facial thirds. My concern is about how a quantifiable base of the sum of all three thirds divided can be reliably accurate insofar as to properly measure ...
3
votes
0answers
86 views
Elementary number theory proofs
I am a freshman studying computer science, and I am supposed to solve this problem for my '(introduction to) elementary number theory' course. Could someone give me a hint or two on how to solve the ...
1
vote
1answer
38 views
Does there exist a composite, deficient, odd number that is divisible by the sum of its proper factors?
Consider $n \in \mathbb{N}$.
Define the aliquot sum function $s(n)$ to be the sum of the proper divisors of $n$ (the divisors not including $n$ itself). Call $n$ deficient if $s(n) < n$, abundant ...
2
votes
1answer
74 views
A problem regarding polynomials $x^t+1$ [on hold]
For what value of $t$ is $x^t+1$ divisible by $x^{15}+x^{14}+1$. How to find it?
5
votes
1answer
62 views
Two friends have $2$ natural written on their forehead. One is $2$ times the other + $1$. They can raise their hands.
The problem:
Two friends have $2$ natural written on their forehead. One of them is $2$ times the other + $1$. Let's call them $X$ and $2X + 1$. They have to come up with a strategy to guess their ...
6
votes
2answers
101 views
Show that $(\binom{p^2}{p} -p ) $ is divisible by $p^5$, for every prime number $p, p\ge 5$
Show that $(\binom{p^2}{p} -p ) $ is divisible by $p^5$, for every prime number $p, p\ge 5$.
I have a combinatorics problem, and this is what it reduces to. I am not quite sure how to link the fifth ...
-1
votes
2answers
33 views
Divisibility Theory [on hold]
The question asks me to prove that no integer of the $8k+5$ where k is a positive integer, can ever be a perfect square.
0
votes
1answer
7 views
Return the number of integers within the range of a and b that are divisible by x
So I have a question here:
Return the number of integers within the range of a and b that are divisible by x.
So I have, a = 0, b = 17 and x = 17.
Apparently the answer is 2.
I understand that 17 /...
0
votes
1answer
53 views
Number of divisors of $ 20^{20} $ with exactly $20$ divisors
How many positive integers $x$ with $x\mid 20^{20}$ have exactly $20$ divisors ?
3
votes
4answers
136 views
+50
A simple doubt in number theory problem.
I considered an even number $n\geq 10$, where it is divisible by some positive integer $k$.
Also, $k$ divides $\frac{n}{2}$. Then $n = kq\implies k\cdot\frac{q}{2} = \frac{n}{2}$.
Can we say that $q$...
0
votes
0answers
51 views
If $y^2-x^2\bigm|2^ky-1$ and $2^k-1\bigm|y-1$ then $y=2^k$ and $x=1$
Suppose that $k\geq2$ and $0<x<y$ and $y^2-x^2\bigm|2^ky-1$ and $2^k-1\bigm|y-1$. Is it necessarily the case that $x=1$ and $y=2^k$?
I've tested this up to $k\leq50$ and $y\leq10000$ but I ...
2
votes
4answers
76 views
Find all pairs $(m, n)$ of positive integers such that $m$ divides $8n+1$ and $n$ divides $8m+1$
I've found the pairs $(1,3),(1,9),(3,25)$ and $(13,21)$ up to order. But I have no idea how to prove that there are not other solutions. Any hints...? I've been trying for a few days but all I came up ...
3
votes
1answer
123 views
Are are infinitely many intimate pairs of integers?
Using the standard statistical definitions, the variance of $x_1, x_2, \ldots, x_n$ and the squared errors about its mean $\mu$ are given by $\sigma^2 = \sum_i(x_i - \mu)^2/n$ and $\delta_2 = \sum_i(...
1
vote
1answer
25 views
Determine a property of $S_b(n)$, which is the sum of the digits of $n$ when $n$ is expressed in base $b$
The original question Let $S_b(n)$ be the sum of the digits of $n$ when $n$ is expressed in base $b$. was asked by Anson Chan on Jan. 24, 2019. Since it was deemed to not have enough context, it was ...
2
votes
2answers
80 views
Proof for divisibility of polynomials. [closed]
I have no idea how to proceed with the following question. Please help!
"Prove that for any polynomial $ P(x) $ with real coefficients, other than polynomial $x$, the polynomial $ P(P(P(x))) − x $ is ...
2
votes
3answers
41 views
Prove $a^n+1$ is divisible by $a + 1$ if $n$ is odd [duplicate]
Prove $a^n+1$ is divisible by $a + 1$ if $n$ is odd:
We know $a$ cannot be $-1$ and the $n \in \mathbb{N}$.
Since $n$ must be odd, we can rewrite $n$ as $2k+1$. Now we assume it holds for prove that ...
1
vote
0answers
34 views
A mysterious fact related to digital root of a 'special incorrect division' and 'correct division'.Whats the reason behind it?
I observed that the digital root of an 'incorrect division' obtained by dividing a number in a 'special way'/'particular manner' and the digital root of the correct division are always same.
The ...
5
votes
3answers
87 views
$8^n-3^n$ Divisible by 5 - Proof Verification.
Statement: $\frac{8^k-3^k}{5}=M, M\in\mathbb{N}$
Base case: $P(1): \frac{8-3}{5}=1\in\mathbb{N}$
Assume $P(n): \frac{8^n-3^n}{5}=N$
Then, $P(n+1)=8^{n+1}-3^{n+1}=5K$, where $K$ is in terms of $M$
...
0
votes
1answer
21 views
Given a number $N$ and two numbers lower than $N$, what are all of the combinations of those numbers that sum to $N$?
I tried looking around the website for a while but I was unable to find anything that matched this problems specifically. So if someone here knows of a question that is the same as mine, please link ...
2
votes
3answers
242 views
Can divisibility rules for digits be generalized to sum of digits
Suppose that we are given a two digit number $AB$, where $A$ and $B$ represents the digits, i.e 21 would be A=2 , B=1. I wish to prove that the sum of $AB$ and $BA$ is always divisible by $11$.
My ...
1
vote
1answer
33 views
Prove that if x is odd and y is even, then gcd(x+y,x-y)=gcd(x,y)
It is trivial to prove that gcd(x,y) divides gcd(x+y,x-y). How is it possible to prove gcd(x+y,x-y) divides gcd(x,y)? I don´t know how to use the fact that x is odd and y is even. Can anybody help me ...
2
votes
1answer
34 views
If $a \mid c$ and $b \mid c$ where $a, b, c \in \mathbb{N}$, under what conditions does it follow that $a \mid b$?
The following question is pretty basic, and the underlying idea was used in the "proof" of a statement in this hyperlinked answer to another MSE question.
The question is as follows:
If $a \mid c$ ...
1
vote
6answers
102 views
$31$ divides to $28!+233$? [duplicate]
How to prove that $31$ divides to $28!+233$?
I have tried to use Wilson's theorem and the primes decomposition theorem but I have not had success.
Thanks for your help
0
votes
2answers
32 views
Does division by zero imply a different type of division in this situation
Firstly, I would like to apologize if this is somehow addressed in one of the many many explanations about why division by 0 is impossible that appear on this site. I have not yet found one that ...
1
vote
2answers
45 views
Number theory divisibility check question
N = $2^{744} - 1$.
Prove N is divisible by $2^{93}+2^{47}+1$. I have no idea how to proceed. (edit: removed first part as I got the answer)
1
vote
1answer
31 views
Is there a name for the largest factor $f$ of a number $n$ so that $n/f \ge f$?
TL;DR: Is there a name for the largest value of $f$ for which $f|n$ and $n/f \ge f$? Or a name for the smallest value of $f$ for which $f|n$ and $n/f < f$?
Additional clarification. This question ...
4
votes
0answers
65 views
On two nested radicals and divisibility
The last days I was playing around with two nested radicals which, as I learned here, can be simplified:
$$u(x) =\sqrt{x + \sqrt{x +\sqrt{x +\sqrt{x +...}}}} = \frac{1}{2}(1+\sqrt{1+4x})$$
$$l(x) = \...
1
vote
1answer
60 views
Find all triplets $(a,b,c)$ less than or equal to 50 such that $a + b +c$ be divisible by $a$ and $b$ and $c$.
Find all triplets $(a,b,c)$ less than or equal to 50 such that $a + b +c$ be divisible by $a$ and $b$ and $c$.(i.e $a|a+b+c~~,~~b|a+b+c~~,~~c|a+b+c$) for example $(10,20,30)$ is a good triplet. ($10|...
1
vote
3answers
94 views
Find the remainder when the polynomial $1+x^2+x^4+x^6+…+x^{22}$ is divided by $1+x+x^2+x^3+…+x^{11}$
Find the remainder when the polynomial $$1+x^2+x^4+x^6+....+x^{22}$$ is divided by $$1+x+x^2+x^3+...+x^{11}$$
$1+x^2+x^4+x^6+....+x^{22}=\frac{x^{24}-1}{x^2-1}$
$1+x+x^2+x^3+...+x^{11}=\frac{x^{12}-...
0
votes
2answers
56 views
Prove that if $f(x)$ divides $g(x)$ and $f(x)$ divides $h(x)$, then $f(x)$ divides $s(x)g(x) +t(x)h(x)$.
Let $F$ be a field. Prove that for all polynomials $f(x), g(x), h(x) \in {F}[x]$, if $f(x)$ divides $g(x)$ and $f(x)$ divides $h(x)$, then for all polynomials $s(x), t(x)\in {F}[x]$, $f(x)$ divides $s(...
0
votes
0answers
40 views
Non-trivial divisors
I want to find out the number of integers whose biggest non-trivial divisor is exactly $k$ times the smallest non-trivial divisor of that integer.
My thoughts are, that the smallest divisor $n$ has ...
3
votes
3answers
47 views
How to eliminate prime factors from algebraic integers?
I'm trying to eliminate prime factors from algebraic integers.
Is the following true without further restrictions? And how can I prove it?
Let $p,N,M\in\mathbb Z$, let $p$ be prime such that $gcd(p;N)...
-3
votes
0answers
98 views
Nice tuples! A number theory problem. [duplicate]
How many tuples $(a,b,c)$ could be found so that $a+b+c$ is divisible by $a$ and $b$ and $c$.
$a, b, c\; $ are natural numbers less than or equal to $50$.
I'm stuck on this homework problem. ...
1
vote
1answer
45 views
Divisibility of fourths by seven
I am otherwise very good in mathematics, but recently I came upon a problem that I just can't solve. Do you have any idea how to solve it?
If $a^2 + b^2 + c^2$ is divisible by 7, prove that $a^4 + b^...
1
vote
2answers
106 views
Prove that $\frac{(72!)}{(36!)^2}-1$ is divisible by 73 [closed]
Prove that $\frac{(72!)}{(36!)^2}-1$ is divisible by 73.
My approach is as follow $73n=\frac{(72!)}{(36!)^2}-1$ I tried remainder theorem but could not prove it.
1
vote
2answers
27 views
Prove that $M_n\mid (i+n)(i-n)$ and $M_n\mid(i+n-1)(i-n+1)$
My friend gave me a problem:
Prove that if $M_n$ is the $n^\text{th}$ odd number, then for all integers $i$, $$M_n\mid (i+n)(i-n)\quad\text{and}\quad M_n\mid(i+n-1)(i-n+1)\tag*{$[1]$}$$
The ...
0
votes
1answer
59 views
How l can draw Hasse diagram
How can l draw a Hasse diagram of the divisibility relation, when $$B=\{2,4,5,6,7,10,18,20,24,25\}$$
Would any help, thank you.
1
vote
2answers
50 views
How to determine the smallest value of $N=n^4+6n^3+11n^2+6n$ if 13 and 19 both divide N?
I tried to solve for an integer solution by making N equal to multiples of 247 but this is not leading me anywhere. I then tried using the tests for divisibility which did not seem to lead me anywhere ...
2
votes
3answers
103 views
Hopeless Numbers
Beatriz Viterbo has called a positive integer which is not divisible by any of the ($2^n$, where $n$ is the number of its digits) numbers that result by introducing a plus or minus sign to the left of ...
0
votes
1answer
15 views
distribute items into containers evenly without splitting
Im trying to figure out how to place a number of items into containers evenly but without splitting.
Easy example:
11 items, 2 containers
11/2 = 5.5
so even distribution would look like this (...
4
votes
3answers
153 views
Isn't there any divisor $k$ of $n^4$ such that $n^2-n<k<n^2$?
I did some experiment with my Python script to find a number which could divide $n^4$ in this interval ($n^2-n$, $n^2$).
I watched the form of prim factors of the numbers in this ($n^2-n$, $n^2$) ...
1
vote
7answers
81 views
How to find divisibility of a very large number
I was asked this question in a test:
The number $111111...111$ ($1$ comes 91 times) is a:
A) Prime number
B) Composite Number
C) divisible by $\frac{10^7 -1}{9}$
The answer is B ...
-1
votes
1answer
66 views
Prove that for every positive integer $n>0$, $3\sum\limits_{i=1}^n i^5 $ is divisible by $\sum\limits_{i=1}^n i^3$ [closed]
Can you help me with this problem :
Prove that for every positive integer $n>0$,
$3\sum\limits_{i=1}^n i^5 $ is divisible by $\sum\limits_{i=1}^n i^3 $
1
vote
2answers
149 views
Describe the Natural density of $p$ which divides natural numbers of the form $n^2+1$?
We want to find the numbers that divide natural numbers in the form of $n^2+1$ and solve for their natural density.
Using Wolfram Mathematica, I found divisors from $n=0$ to $1000000$ and eliminated ...
1
vote
2answers
54 views
Prove that if there are integers $m$ and $n$ such that $am +bn =1$ then $a$ and $b$ are coprime.
Suppose $a,b \in \mathbb{N}$. Prove that if there are integers $m$ and $n$ such that $am +bn =1$ then $a$ and $b$ are coprime.
I came up with the following proof, but I am sure a shorter argument ...
1
vote
1answer
40 views
How to prove that if $(ab,n)=1$ then, $(r,n)=1$? [duplicate]
Let $ab=nq+r$ where all variables represent integers with $0\leq r<n$. If $(ab,n)=1$ then how to prove that $(r,n)=1$? I need to prove this to help me understand the proof of Euler's theorem better....
2
votes
3answers
136 views
Why does the statement “p is prime if it is divisible by only itself and 1” define only one prime number? [closed]
I'm having a bit of trouble understanding why this incorrect definition of primality only defines one prime number.
"p is prime if it is divisible by only itself and 1."
My understood definition of ...
0
votes
0answers
35 views
Prove that $(a^2b^2)^k + (b^2c^2)^k + (c^2a^2)^k$ is divisible for $\dfrac{1}{2}(a^4 + b^4 + c^4)$.
If $a$, $b$ and $c$ are a Pythagorean triple then prove that $(a^2b^2)^k + (b^2c^2)^k + (c^2a^2)^k$ is divisible for $\dfrac{1}{2}(a^4 + b^4 + c^4)$ for all integer $k \ge 2$.
I cannot think of any ...
4
votes
2answers
63 views
Show that $m\mathbb{Z}$ is a subgroup of $n\mathbb{Z} \iff m|n $
Show that $m\mathbb{Z}$ is a subgroup of $n\mathbb{Z} \iff n|m $
I think my solution for one way of this is correct:
$\Rightarrow$ Suppose $m \mathbb{Z}$ is a subgroup of $n\mathbb{Z}$
, then $m \...
