Questions tagged [divisibility]
This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.
4,939
questions
0
votes
1answer
22 views
Parity of Euler's totient function
Let $S$ be a set of all numbers $k$ such that $(n, k) = 1, 1 \leq k \leq n.$
Of course, smallest element in $S$ is (by definition) $1$ and largest is $n - 1$ (since $\text{gcd}(n - 1, n) = 1$).
In ...
0
votes
1answer
18 views
Polynomial Division Under Certain Remainders
Let $P(x)$ be a polynomial such that when $P(x)$ is divided by $x-17$, the remainder is $14$, and when $P(x)$ is divided by $x-13$, the remainder is $6$. What is the remainder when $P(x)$ is divided ...
1
vote
1answer
38 views
Use Fermat's Little Theorem
Find a number $0 \leq a < 73$ with $a≡9^{794}\mod 73$.
I know that $a$ and $73$ are relatively prime and $a^{72}≡1 \mod73$. But I couldn't use the theorem.
Can someone help me please?
0
votes
1answer
16 views
How many solutions are there to the congruence
How many solutions are there to the congruence
X^4 + 5X^3 + 4X^2 - 6X - 4 ≡ 0 (mod11) with 0 ≤X ≤11?
I need to find that that if there are 4 solutions or there are fewer ...
0
votes
0answers
19 views
Diophantine equations that involve Gregory coefficients: a computational exercise
In this post, for integers $k\geq 1$, we denote the Gregory coefficients as $G_k$. Wikipedia has an article for Gregory coefficients, are known as reciprocal logarithmic numbers (I add this as ...
-3
votes
0answers
38 views
The length of the algorithm [closed]
The "3n + 1 algorithm" works as follows.
Start with any number n. If n is even,
divide it by 2. If n is odd, replace it with 3n + 1
So, for example, if we start
with 5, we get the list of numbers
5,...
0
votes
3answers
32 views
Divisibility of $a_{24}$ by 7. ($a_n=\underbrace{999\cdots9 }_{n \text{ times}})$
Question: By which number is $a_{24}$ divisible by?
Where $a_n=\underbrace{999\cdots9 }_{n \text{ times}}$
The solution says the answer is $7$. Here's what is given:
$$a_{24}=\underbrace{999\...
0
votes
2answers
57 views
Find solutions of $m=\frac{n^2}{(n-m-1)\lambda+n}$ where $n,m,\lambda$ are postive integers,$1\le\lambda \le n-1$ and $m\mid n$.
I am considering the following equation
$$m=\frac{n^2}{(n-m-1)\lambda+n}$$
where $n,m,\lambda$ are postive integers, $1\le\lambda \le n-1$ and $m\mid n$. If $m=n$, then
$$\frac{n^2}{(n-n-1)\lambda+n}...
0
votes
1answer
51 views
Total ordering - Partially ordered set
A = {2,4,5,6,9,10,12,18,30,36,60,72}
R={(a,b) | a divides b}
I want to find a total order about partially ordered set(A,R).
If there are multiple possible values, select a large number first.
In ...
0
votes
0answers
25 views
Draw a hasse diagram about inverse R - divisibility
R = {(a,b) | a divides b}
R is partially ordered set for set A.
When I draw a hasse diagram about [inverse R], maybe I just change the top and bottom of the hasse diagram about [R].
Is it right?
0
votes
0answers
51 views
How to draw hasse diagram - divisibility - R and inverse R
I don't know how to draw the Hasse diagram for divisibility on the sets.
A = {2,3,4,5,6,9,10}
R is partially ordered set for set A. R = {(a,b) | a divides b}
How to draw a hasse diagram about R and ...
1
vote
1answer
47 views
Unique solution of the equation $\prod_{i=1}^m(a_i+1)\prod_{i=1}^n(b_i)=\prod_{i=1}^m(a_i)\prod_{i=1}^n(b_i+1)$
Let $a_i$ be a sequence of $m$ distinct odd integers and $b_i$ a sequence of $n$ distinct odd integers.
We have to prove that,
$$\prod_{i=1}^m(a_i+1)\prod_{i=1}^n(b_i)=\prod_{i=1}^m(a_i)\prod_{i=1}^n(...
-1
votes
0answers
17 views
Proof GCD(m,n) = GCD(m,n-m) [duplicate]
I need to prove that statement but I can't think of a way to do it. m and n are integers and m is different from 0.
0
votes
0answers
21 views
About the characterization of solutions of an equation that involves particular values of the Dedekind psi function
In this post we denote the Dedekind psi function as $\psi(m)$ for integers $m\geq 1$. This is an important arithmetic fuction in several subjects of mathematics. As reference I add the Wikipedia ...
2
votes
2answers
38 views
If $R$ is a UFD, $p(x)\in R[x]$ and $a/b$ is a root of $p(x)$ in the fraction field, then we have $p(x)=(bx-a)q(x)$ for $q(x)\in R[x]$.
Suppose $R$ is a UFD and $p(x)\in R[x]$ a polynomial of degree $\ge 1$. Suppose $\frac ab$ is in the fraction field $K$ of $R$, with $a$ and $b\in R$ and $\text{gcd}(a,b)=1$, and such it is a root ...
-1
votes
4answers
90 views
Last 3 digits of $2^{2017}$
Find the last three digits of $2^{2017}$
My approach:
As $125 \times 8=1000$ we have the congruence modulo $$x \equiv 2^{2017}(mod \: 1000)$$ is equivalent to the equations
$$x \equiv 2^{2017}(mod \:...
0
votes
0answers
52 views
How to check if a large number is divisible by a Prime Number? [closed]
How to check if a large number is divisible by a Prime Number?
Are there some divisibility rules for this?
1
vote
1answer
38 views
Finding conditions such that $4b^2 > a^2 > 3b^2$ and $b \mid (a^2-1)$ imply $b=(a+1)/2$
Consider the set of odd positive integers $a$ and $b$ such that $4b^2 > a^2 > 3b^2$ and $b \mid (a^2-1)$.
Brute-force computation suggests that $a=2b-1$ is the only solution for “most” such $b$,...
0
votes
1answer
35 views
Consider set $\mathbb{Z}[\sqrt{-5}] = \{a+b\sqrt{5}i : a,b \in \mathbb{Z} \}$ show that it is a ring [duplicate]
Consider set $\mathbb{Z}[\sqrt{-5}] = \{a+b\sqrt{5}i : a,b \in \mathbb{Z} \}$.
My task is to show some features listed below:
Show that $\mathbb{Z}[\sqrt{-5}]$ is a ring.
I would like to show that ...
0
votes
2answers
28 views
Proof of divisibility by induction [duplicate]
I've recently come across a divisibility problem that I am unable to solve. I know that most of these types of problems have fairly straightforward proof-by-induction solutions -- but for this ...
4
votes
1answer
129 views
On a symmetric equation over the integer lattice that involves the Euler's totient function
I would like to know hints or a proof, or counterexamples, for the conjecture that I've stated in the Question below. I'm interested in this in an attempt to continue the study of a question that I've ...
0
votes
1answer
47 views
Find the number of incongruent solutions
Let $p$ be a prime number. Find the number of incongruent solutions of
$$ x^{p^5}-x+p\equiv0\mod p^{2020}.$$
Let $f(x) = x^{p^5}-x+p$. Because of $f '(x)$ different from zero mod $p$. Then I say
$$f(...
0
votes
0answers
41 views
For which $n\in N$ do we have $x^2+x+1|(x-1)^n -x^n-1$.
For which $n\in N$ do we have
$$x^2+x+1|(x-1)^n -x^n-1$$
This question is from the book 'Problem Solving Strategies'
Here is the solution
Can anyone please explain the solution in detail?
I am ...
1
vote
1answer
76 views
Prove any set S of three integers contains a pair $x\neq y$ such that $x^3y-xy^3$ is divisible by 10.
Prove any set S of three integers contains a pair $x\neq y$ such that $x^3y-xy^3$ is divisible by 10.
My attempt was :
By the division algorithm, every integer $n$ can be written as $n = 10q + r,$ ...
2
votes
1answer
27 views
Find the smallest value $n$ such that there exists a non-empty subset of any set of n positive integers whose sum is divisible by 1001
Find the smallest value of $n$ such that for any set of $n$ positive integers, there exists a non-empty subset of the set whose sum is divisible by $1001$
This is sort of a follow up on my last post ...
0
votes
0answers
17 views
Proving that you can pick a group of numbers from a set of 4 natural numbers that divide 4 [duplicate]
Prove that for any set of $4$ natural numbers, it is possible to pick a group of numbers (can contain $1-4$ numbers) from the set such that the sum of the group is divisible by $4$.
I tried to ...
-1
votes
2answers
24 views
$f(x)$ is monoic polynomial , prove that if $f(k), f(k + 1),…, f(k + p)$ is not divisible by $p + 1$, then $f(x) = 0$ has no rational solution. [duplicate]
Given a monic polynomial $f(x)$ of degree $n$ over $Z$ and $k, p \in N$ , prove that if none of the numbers $f(k), f(k + 1),..., f(k + p)$ is divisible by $p + 1$, then $f(x) = 0$ has no rational ...
-1
votes
2answers
235 views
Related prime factors [closed]
Do there exist a positive integer $N$ and three primes $p_1<p_2<p_3$ such that the only prime factors of $N-p_1$ is $p_2$, the only prime factors of $N-p_2$ are $p_1,p_3$ and the only prime ...
-1
votes
3answers
54 views
Prove that for all integers $n$, $3$ does not divide $n^2-5$ using modular arithmetic. [duplicate]
I am having trouble proving that for all integers $n,\ 3$ does not divide $n^2-5$ using modular arithmetic. I know that $3\not\mid n^2-5$ means $n^2\not\equiv 5\pmod 3$. But I'm not sure how to start ...
0
votes
1answer
50 views
Solutions to Diophantine equation $\frac{1}{n}+\frac{1}{p}=\frac{1}{N}$
For each prime $p$ there seems to be a uniqe solution $n=(p-1)p$ to the Diophantic equation
$\frac{1}{n}+\frac{1}{p}=\frac{1}{N}$.
Is that right and if so, how to prove the unicity?
In spite of my ...
3
votes
2answers
103 views
Find the all positive integer solutions $(a,b)$ to $\frac{a^3+b^3}{ab+4}=2020$.
Find the all positive integer solutions of given equation
$$\frac{a^3+b^3}{ab+4}=2020.$$
I find two possible solutions, namely $(1011,1009)$ and $(1009,1011)$, but the way I solve the equation was ...
3
votes
2answers
51 views
If $\alpha, \beta$ are the roots of the equation $x^2-(p+1)x+1=0.$ show that $\alpha^n + \beta^n$ is not divisible by $p$ $(p \ge3)$
Let $p \ge 3$ be an integer and $\alpha, \beta$ are the roots of the equation $x^2-(p+1)x+1=0.$ Using mathematical induction show that $\alpha^n + \beta^n$
(i) is an integer
(ii) is not divisible by ...
0
votes
2answers
175 views
How to find k'th integer not divisible by n?
Although this was a programming question I want the mathematical intuition behind it. So we were given two numbers n and k. We were askd to find out k'th number not divisible by n. For example
n=...
2
votes
3answers
89 views
When $ab/(a+b)$ is an integer, where $a,b$ are positive integers.
When $ab/(a+b)$ is an integer, where $a,b$ are positive integers?
...
0
votes
2answers
43 views
Prove that for odd $n > 1$ , $3^{n} + 1$ is not divisible by $n$ [duplicate]
Prove that for odd $n > 1$ , $3^{n} + 1$ is not divisible by $n$.
There's a hint but I can't find any use for that.
hint: If $a$ and $b$ are coprime with $m$ and $a^{x} \equiv b^{x}$ (mod $m$) ...
2
votes
1answer
48 views
I don't know if I'm correct.
Problem:
Let $a,b\in\Bbb N$ with $a\cdot(a,b)=b\cdot[a,b]$ where (a,b) means the greatest common divisor of a,b and [a,b] means the smallest common multiple of a,b prove that there are an infinite ...
0
votes
2answers
57 views
A Divisibility Question
Consider $f(x) = x^5 + 2x^4 + x^3 + 2x^2 + x + 1 \in \mathbb{F}_3[x]$. I see that $f(x) = (x^2+x -1)\cdot(x^3 + x^2 + x - 1)$, both of which are irreducible / prime polyonimals (Recall that since $\...
3
votes
2answers
68 views
School-level problem on divisibility
I encountered the problem to show that there is an integer of the form $11111\ldots 11$ divisible by $2021$. It is easy to show that there is a number of the form $111 \ldots 11 \cdot 10^k$ ...
1
vote
0answers
105 views
Is it true or can it be proven that $\frac{n}{\varphi(n)} \geq \operatorname{rad}(n)$?
The title says it all:
Is it true or can it be proven that $\frac{n}{\varphi(n)} \geq \operatorname{rad}(n)$?
Here $n$ is a natural number, $\varphi(n)$ is the Euler-totient function of $n$, and $\...
-1
votes
1answer
37 views
Long division answer differs to calculator answer
Can someone make sure I'm not going mad, I'm doing very simple long division: $271÷15$.
I work it out as $18.06\bar 3$ but a calculator returns $18.0\bar 6$?
What's going on here? Do I have a ...
1
vote
2answers
42 views
Solve equation with constrain on number of decimals?
Given this equation:
11 x + 102 y = 100
How can I find all possible solutions for which the following condition is satisfied:
...
1
vote
3answers
42 views
Find $a,b \in \mathbb{N}$ with $\mathrm{lcm}(a,b)=12\gcd(a,b)\,$ and $\,a\bmod b = 5$
Find $a,b \in\mathbb{N}$ such that:
Remainder of $a$ divided by $b$ equals $5$
$\mathrm{lcm}(a,b)=12\gcd(a,b)$
I don't know how or where to start. The most similar problem I found was Find ...
0
votes
1answer
59 views
Find the value of the prime $p$ knowing that $p>5$ and $p│(3^{p+1} +5^{p-1} + 1)$
I am trying to find the value of $p$, a prime number of which we only know that $p>5$ and:
$p│(3^{p+1} +5^{p-1} + 1)$
This is part of a collection of exercises regarding divisibility, Fermat's ...
3
votes
3answers
44 views
A function divisible by $p$
I want to ask about what is the intuition for making functions like these
$4^n+2$ is divisible by $3$
$ 2^{4n+2}+3^{n+2}$ is divisible by $13$
And if so, how can I make my own ones? Thank you all ...
-3
votes
0answers
21 views
2014 doors problem [duplicate]
$2014$ numerated doors. All doors are closed.
Person $1$ opens all the doors.
Person $2$ closes $2,4,6,8,...$ doors.
Person $3$ changes (closes if door is open and vice versa) $3,6,9,12....
1
vote
1answer
77 views
There are two positive integers of the form $p-n^2$ such that one divides the other.
Let $p>3$ be a prime number. Consider the numbers of the form $p - n^2$ where $n = 1 , 2 , 3 , ... , \lfloor\sqrt{p}\rfloor$. Show that there exist two such numbers, $a$ and $b$, that $a | b$.
I ...
2
votes
3answers
80 views
Dividing polynomial $f(x^3)$ by $x^2+x+1$
Given two polynomials with real coefficients $g(x)$ and $h(x)$.
Additionally, $x^2+x+1$ is a factor of $f(x^3)= h(x^3)+xg(x^3)$.
Prove that $x-1|h(x)$ and $x-1|g(x)$
I have tried to solve it by ...
1
vote
2answers
60 views
Proving that when $n$ is not a power of 2, $\exists k, 0 < k < n$ such that $\binom{n}{k}$ is odd
So I had a read over this question here which showed that any $n$ that is a power of two has it that $\binom{n}{k}$ is an even number for $0 < k < n$.
Now I am wondering if for every other $n$,...
-1
votes
0answers
32 views
Prove: $\gcd(a,b)=1\ $ and $\ n>ab-a-b \implies\exists\ x,y\ \epsilon \ \mathbb{N} \ /ax+by=n$ [duplicate]
Let be $a,b,n\ \in \ \mathbb{Z} \ $with $ a,b>1 $
We look at the equation $ax+by=n$
Prove that if $\gcd(a,b)=1\ $ and $\ n>ab-a-b \implies\exists\ x,y\ \in \ \mathbb{N} : ax+by=n$
I ...
7
votes
1answer
160 views
Help with this problem about a constructed number, that is from an arbitary n numbers, and that is divisible by a prime
Let $p$ be a prime number, and $n$ be an integer such that $n \geq p$. Let $a_1,...,a_n$ be arbitrary integers. Let $s_0 = 1$, and for every $k \ge 1$, let $$s_k=|\{B \subset \{1,2,...,n\} : p\mid\...
