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
1answer
76 views

When does $a\mid c$ and $b\mid c$ imply $ab\mid c$? [duplicate]

For example, $$2\mid12,3\mid12,6\mid12$$ But, $$4\mid12,6\mid12,24 \nmid 12$$ When does it work?
0
votes
2answers
69 views

How do I know that $3$ and $2 + \sqrt{-5}$ are not associates in $\mathbb Z[\sqrt{-5}]?$

How do I know that in $\mathbb Z[\sqrt{-5}],$ the elements $3$ and $2 + \sqrt{-5}$ are not associates? Thanks a lot.
0
votes
0answers
21 views

I'm trying to prove that for all a,b integers gcd(a,b)=1 iff gcd(a+b,ab)=1 but I'm unsure of my proof for the converse. [duplicate]

This is my proof: $\Rightarrow )$ Supose that $\gcd(a,b)=1$. We are to show that $\gcd(a+b,ab)=1$. Since $\gcd(a,b)=1$, then $1\mid a$ and $1\mid b$. By a lemma, $\forall \alpha, \beta \in \mathbb{Z}...
0
votes
2answers
26 views

How to use long division to compute the reciprocal $1/Q(s)$ of a generic polynomial?

In these notes (pag 3, pdf alert) the author observes that, given a complex polynomial $Q(s)=q_0 + q_1 s+ ... + q_m s^m$ with $q_0\neq0$, "using the long-division algorithm", we have $$\frac{1}{Q(s)}=...
2
votes
2answers
36 views

finding all numbers $a,b$ that divide $c$ but product of $a$ and $b$ does not divide $c$

Let $a,b,c\in \mathbb{Z}$, such that $a$ and $b$ are relatively prime, and both $a$ and $b$ divide $c$. Prove that in this case $ab$ divides $c$. Find all numbers such that $a$ and $b$ divide $c$ but $...
1
vote
2answers
54 views

Is there a division-by-zero problem when we divide by pure imaginary numbers?

I was wondering, if $\frac{x}{0}$ is undefined, is $\frac{x}{i}$ undefined too? Considering that the real part of $i$ is zero, is the $\frac{x}{0+i}$ some form of division $x$ by $0$? Does $\frac{x}{...
-1
votes
1answer
37 views

given 9 consecutive naturals, no partition into two sets will give set one product = set two product

I know another user already asked this but I want to do another approach. Can we list the numbers as $y, y+1, y+2, y+3, y+4, y+5,y+6,y+7,y+8$ and go case by case for the partition into a set with $...
0
votes
2answers
50 views

If $3\mid mn$, then $3\mid m$ or $3\mid n$

I'm currently studying proofs and fundamentals, I'm reading a book by my own and I saw this problem. Theorem Let $m$ and $n$ be integers. If $3\mid mn$, then $3\mid m$ or $3\mid n$. My proof was the ...
0
votes
1answer
107 views

Positive integers $n$ with $n^5 - 5n^3 + 5n + 1 | n!$

Find all positive integers $n$ such that $n^5 - 5n^3 + 5n + 1 | n!$ I know that $ n^5-5n^3+5n+1=(n+1)(n^4-n^3-4n^2+4n+1)$, but I have no idea where to go from here. This was from a local contest. ...
3
votes
1answer
30 views

$P,R \neq 0$ are polynomials with rational coefficients. Show that there exists a polynomial $Q$ such that $P(X) | Q(R(X))$

Given any non-zero polynomials $P,R$ with rational coefficients, show that there exists a polynomial $Q \neq 0$ with rational coefficients such that $P(X)|Q(R(X))$. I would like to know if my solution ...
1
vote
4answers
75 views

Number of ordered Pairs satisfying $4^m-3^n=1$

Find the Number of ordered Pairs $(m,n)$ of positive integers satisfying $4^m-3^n=1$ Mt try: Trivially $m=n=1$ satisfies Let $m \gt 1$ $$4^m-3^n=(1+3)^m-3^n=1$$ $\implies$ $$3\binom{m}{1}+3^2\binom{...
1
vote
0answers
45 views

Iran Mathematics Olympiad Problem [duplicate]

If $x,y$ are Positive integers such that $3x^2+x=4y^2+y$ Prove that $x-y$ is a Perfect Square My try: We have $$3x^2+x-(4y^2+y)=0$$ a Quadratic in $x$ So $$x=\frac{-1+\sqrt{1+12(4y^2+y)}}{6}$$ ...
3
votes
3answers
131 views

How to choose a special modulus to show that $6n^3 +3 = m^6$ has no solutions in the integers

I was stuck on a problem from Mathematical Circles: Russian Experience, which reads as follows: Prove that the number $6n^3 + 3$ cannot be a perfect sixth power of an integer for any natural number ...
1
vote
2answers
109 views

Equations involving particular values of the Dedekind psi function and powers of the kernel function

In this post we denote the Dedekind psi function as $\psi(m)$ for integers $m\geq 1$. As reference I add the Wikipedia Dedekind psi function, and [1]. One has the definition $\psi(1)=1$, and that the ...
1
vote
1answer
54 views

On composite numbers $n$ such that $n^2\equiv 1\text{ mod }\psi(n)$, where $\psi(n)$ denotes 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 ...
0
votes
2answers
47 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
21 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
51 views

Use Fermat's Little Theorem [duplicate]

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
33 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 ...
1
vote
3answers
41 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\...
1
vote
2answers
78 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
59 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
29 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
56 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
54 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(...
0
votes
1answer
148 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
47 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
107 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 \:...
2
votes
1answer
42 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
38 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
34 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
155 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
55 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(...
1
vote
1answer
77 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
29 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
27 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
3answers
62 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
56 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
109 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
55 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
249 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=...
1
vote
3answers
95 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
45 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
49 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
111 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
39 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: ...