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
0answers
30 views

Does the polynomial $f(x)=\prod_1^n{x_k}$ divide $\sum_{k=1}^{n-1} \frac{f^{(k)}(x)}{k!}$, where $f^{(k)}(x)=\frac{d^{k}{f(x)}}{dx_1^k}$, for $n>1$?

I have the following conjecture: Let it be a set of distinct positive integers $S=\{x_1,x_2,...,x_n\}$, such that $x_1<x_2<...<x_n$ Let it be $f(x)=\prod_1^n{x_k}$ Let it be $f^{(k)}(x)=\...
-1
votes
2answers
51 views

is it possible to calculate mod of a very long number manually? [closed]

Assuming we found a very old book with more than 1000 years old and there is an extraordinary mathematical pattern in it. Let's say its text has 'many' clear patterns. As an example, concatenation of ...
0
votes
1answer
18 views

Dividing within limits

Assume $\phi \in (0,1)$ and the following condition holds $$\lim_{t\to\infty} \phi^t x_t = 0.$$ Is it true that $$\lim_{t\to\infty} ( \phi x_t - x_{t-1}) = 0?$$ My proof would be like this: From ...
0
votes
0answers
14 views

Is there a more efficient way to calculate “step” division?

I have a base value 16, I need to divide it by the ratio 1.067 6 times to reach the desired outcome value ...
-1
votes
1answer
39 views

Proving a property with the Euclidean division properties [duplicate]

I am trying to prove that any square AND cube number (that is, any number which is the square and the cube of other two numbers, for example $64=8^2=4^3$, I don't know if this has a proper ...
-1
votes
2answers
53 views

Calculating remainder when a polynomial I'd divided by another polynomial

Let $p(x)$ be a polynomial such that when $p(x)$ is divided by $x - 19$ the remainder is $99$, and when $p(x)$ is divided by $x - 99$ remainder is $19$. Find the remainder when $p(x)$ is divided by ...
1
vote
1answer
23 views

Stuck with induction Divisibility

I have seen many on the questions on here about induction divisibilty, but I haven't found any question that covers the doubt that I'm having. The preposition says: "For any integer n $\leq$-3, 8 ...
0
votes
2answers
29 views

$a,b \in R$ a ring. If $a | b$ in $R$ then $bR\subseteq aR$?

I was reading some theory on ring theory and came across "ideals". Now somewhere the following was mentioned : $a,b \in R$ a ring. If $a|b\; (in R)$ then $bR\subseteq aR$ , and I have no idea as how ...
1
vote
1answer
34 views

Divisibility of Coefficient Related to Cyclotomic Integer

In this blog, I found the following lemma- Lemma 4: Coefficients of corresponding powers of $(α - 1)$ must be congruent mod $λ$ provided all powers are less than the $(λ - 1)$ st. if: $a_0 + a_1(α ...
-1
votes
3answers
50 views

Prove that following is always divisble by 5 [closed]

I am not getting how to prove that $1+ 2^{2^{4n-2}}$ is always divisible by 5 for every natural $n > 2$.
-2
votes
1answer
65 views

Proof that if $\gcd(a,p^2)=p$ and $\gcd(b,p^3)=p^2$ then $(ab,p^4)=p^3$ [duplicate]

So $p =ax+p^2y$ and $p^2 =bz+p^3w$ $ax= p-p^2y$ and $bz= p^2-p^3w$ $axbz= p^3-p^4w-p^4y+p^5wy$ $abxz= p^3-p^4(w+y-pwy)$ $abxz+p^4(w+y-pwy) = p^3$ How can I say that $\gcd(ab,p^4) = p^3$ ?
0
votes
0answers
27 views

On solutions of $\varphi(n)=\frac{1}{2n}\sum_{1\leq d\mid n}\varphi(dn)$, where $\varphi(m)$ denotes the Euler's totient function

I wondered if one can to get easily an answer for the following question (I have thought about the other direction $\Leftarrow$). I don't know if it is in the literature, please refer it in comments ...
4
votes
1answer
135 views

Find all the primes $p$, $q$ such that $pq|(5^p - 2^p)(5^q - 2^q)$.

First question for my typing mistake : Find all the primes $p$, $q$ such that $(5^p - 2^p)(5^q - 2^q)|pq$. I am extremely sorry. The question should be : Find all the primes $p$, $q$ such that ...
0
votes
1answer
39 views

relation between concatenation and addition regarding modular arithmetic

This question turned out to be not so clear to me. When we concatenate two numbers (X and Y) the mod 23 of the new number XY is 0. The concatenation of (X-a) and (Y-b) , which is (X-a)(Y-b) also ...
0
votes
0answers
17 views

Semiprimes Totient divisibility

please consider my question: Let $n$ be a positive semiprime, which is known and very very big. Let $\phi(n)$ its Euler Totient value. Consider that $n$ is big enough that factorization is unpractical ...
1
vote
0answers
30 views

On integers $n\geq 1$ for which $n$ divides $\sum_{k=1}^n R_k$, where $R_k$ denotes the $k$-th Ramanujan prime

For integers $n\geq 1$ in this post we denote the Ramanujan primes as $R_n$, see for example the Wikipedia Ramanujan prime or [1]. I don't know if my question is in the literature but I think that it ...
2
votes
1answer
52 views

Prove that $\left(A+B\right)^{2}\nmid A^{2n+1}+B^{2n+1}$

Let it be A and B two coprime positive integers. I know how to prove by induction that $A+B\mid A^{2n+1}+B^{2n+1}$, but I am having a bit trouble proving that $\left(A+B\right)^{2}\nmid A^{2n+1}+B^{2n+...
0
votes
3answers
40 views

Count of 6-digit numbers divisible by 6 but not by 9

Suppose that 6-digit numbers are formed using each of the digits 1,2,3,7,8,9 exactly once. I want the count of such 6-digit numbers that are divisible by 6 but not divisible by 9. I understand that ...
1
vote
2answers
34 views

There is a number, the second digit of which is smaller than its first digit by 4, and if the number

There is a number, the second digit of which is smaller than its first digit by 4, and if the number was divided by the digit's sum, the remainder would be 7. Actually I know the answer is 623 I ...
8
votes
1answer
165 views

Prove there exist n that satisfies $S_n = 1! + 2! + … +n!$ have prime divisor greater than $10^{2020}$.

Prove there exists $n$ such that $S_n = 1! + 2! + .... +n!$ has a prime divisor greater than $10^{2020}$. I started this question like this: For every $n$, $S_n$ have prime divisors only in range $(...
0
votes
0answers
22 views

How can you prove the existence of an integer for ab congruent to 1 (mod p). [duplicate]

With a prime number p and a not equal to 0, how can I prove that there exists an integer b such that ab is congruent to 1 (mod p)? What I have done so far is I know that the GCD(p,a) is either 1 if p ...
0
votes
1answer
78 views

Find all positive integers $n$ such that $n^2 \not\mid (n - 2)!$

Find all positive integers $n$ such that $n^2 \not\mid (n - 2)!$ We have that $\gcd(n - 1, n) = 1$, then $n^2 \not\mid (n - 1)!$ Of course, primes and Carmichael numbers are solutions to this ...
0
votes
0answers
26 views

Divisibility of cyclic sums

Lately I have been studying the divisibility of some cyclic sums, and I was wondering about the following Conjecture Let it be a set of distinct integers $S=\{x_1,x_2,...,x_n\}$. Then, $$\prod_{n=1}...
0
votes
1answer
85 views

For a prime q and positive integers x, y, z, w , q divides yz, q divides xy and q doesn't divide yw implies that q^2 divides xz [duplicate]

I'm attempting to prove that the above statement is true, but am having a bit of trouble. So far I have $qk = yz$ $qj = xy$ I'm not really sure to go from here, but I tried the following I can ...
1
vote
1answer
23 views

Can this congruence rule be generalized? [duplicate]

Let n be a positive integer which representation in base 10 is $a_ka_{k-1}a_{k-2}...a_2a_1a_0$. It's not particularly hard to prove that: $n\equiv a_0\pmod2$ $n\equiv2a_1+a_0 \pmod 4$ $n\equiv 4a_2+...
1
vote
0answers
51 views

Divisibility of odd numbers and its sum of divisors function - Part II

This question is inspired by this earlier one: Divisibility of odd numbers and its sum of divisors function In that question, MSE user Juan Moreno claims to have discovered a proof for the following ...
-1
votes
2answers
28 views

Find all positive integers n such that 20n+2 can divide 2003n+2002 [duplicate]

Could someone give me a hint to this problem please? Here is what I do: $2003n+2002=100(20n+2)+3n+1802$ then I'm stuck at $20n+2|3n+1802$ Please help
0
votes
2answers
38 views

Why the sum of the digits of $9k+a$ (where $k,a\in \mathbb{N}$, and $0<a<8$) is equal to $9l+a$ (where $\mathbb{N}\ni l< k$)?

The sum of the digits of integers that are multiples of $9$ (let's name them $9k$) always add up to another multiple of $9$ (let's call it $9l$). However, I have observed that the sum of the digits of ...
0
votes
1answer
59 views

Prove that $\frac{(mn)!}{(n!)^{m+1}}$ is an integer.

Well I could prove $\frac{(mn)!}{(n!)^{m}{m!}}$ to be an integer by considering there to be m×n different balls and grouping them into m groups consisting of n balls each. But I could not solve this ...
5
votes
2answers
222 views

$a+b \mid ab$ from CMO 1996

The question is from the 1996 Chinese Mathematical Olympiad. I can't find the solutions anywhere online. Find the smallest value of $K$ such that any $K$-element subset of $\{1,2,\ldots,50\}$ ...
0
votes
1answer
35 views

Proof: If a|b, then a|bc.

I’m in the beginning stages of an intro to proofs class, so please bear with me. I’ll write what I have thus far. Proof: Let us suppose a|b. Then there exists an integer b such that b = ak. For a|...
0
votes
6answers
39 views

Prove that for every $n\in\mathbb{N}$, $n^2$ is divisible by 3 or has a form $3k+1$?

I tried to do this by induction, but it doesn't make any sense: $n^2=3k$ or $n^2=3k+1$ option: $(n+1)^2= 3k+2n+1$ option: $(n+1)^2= 3k+2n+2$ Is there any other way on proving this problem?
0
votes
1answer
57 views

Integer solutions to $(a^x - b^y)/(a - b)=c$ [closed]

I would like to know if all integer solutions to $\frac{a^x -b^y}{a - b} = c$, where $c$ is also an integer, are known.
-2
votes
1answer
35 views

Using mathematical induction to prove a divisibility [closed]

I am having trouble to prove that if $a\mid b_1, a\mid b_2, \dots, a\mid b_n$, then $a \mid (b_1 + b_2 + \cdots + b_n)$.
-1
votes
5answers
72 views

For which $n\in\mathbb{N}$ is $(n+2)\mid(n^3+14)$ true? [duplicate]

Tried substitution $n+2=p$, but it only gets more complicated. For $ n=1 $ this is true, but how can I find other $ n$'s?
1
vote
2answers
76 views

Prove that $a^n$ divides $b^n$ implies that $a$ divides $b$. [duplicate]

For $n \ge 1,$ and positive integers $a,b,$ show the following: $\rm (a)$ If $\gcd(a,b)=1,$ then $\gcd(a^n,b^n)=1.$ $\rm (b)$ The relation $a^n\,|\,b^n$ implies that $a\,|\,b.$ This is a ...
-1
votes
3answers
43 views

How to prove that for $p=2n+1$ the expression $3^p+1$ is divisible by 4?

Well, I tried to solve it like this: $3^{2n-1}+1=3\cdot3^{2n}+1\implies3^{2n}$ will be always odd $\implies3^{2n}=2t+1$ $3\cdot3^{2n}+1= 3\cdot(2t+1)+1= 6t+3+1=6t+4=4\ (\frac{3}{2}t+1)$ But because ...
-1
votes
1answer
24 views

Prove if $(a+b)$ divides $(a^2+ab+b^2)$ then $(a+b)^2$ divides $(a^4+b^4)$?

I solved this problem for only $(a+b)$ divides $(a^4+b^4)$. $(a^2+ab+b^2)=k(a+b)$ $\color{red}{(a^2-ab+b^2)}(a+b)^2=a^4+a^3b+ab^3+b^4$ $\color{orange}{(a^2+ab+b^2)}(a-b)^2=a^4-a^3b-ab^3+b^4$ $2(...
0
votes
1answer
70 views

Getting Bigger Factor from Smaller Factor

I have a little confusion. In an article entitled "Torsion Points of Elliptic Curves" (page 15),it is written that- From our equation for the line through $P_1$ and $P_2$, we know that $s_1 = ...
0
votes
2answers
45 views

Are the divisibility tests rooted in number theory?

I had a good look at some mathematics I was doing at age 9. I remembered the divisibility tests we used to do and I thought that I could take a shot at proving them. I managed to prove it for 3. It ...
-3
votes
2answers
41 views

Show that $3$ divides $p-2$ if and only if $3$ divides $p+1$, where $p$ ia a prime different from $3$..

I can observe this but unable to prove this result. If we start by taking the values of $p$ when $3|p+1$ and $p\neq 3$. We get the values of such $p$'s: $5, 11, 17, 23, 41, 47, 53, 59, 71, 83, 89, \...
2
votes
2answers
107 views

Show that $2003$ divides the numerator of $1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + \ldots + \frac{1}{1335}$.

I came up with this problem on a book in number theory : Let $p$ and $q$ be natural numbers such that $$1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + \ldots + \frac{1}{1335} = \frac{p}{q} \,.$$ ...
9
votes
0answers
153 views

A generalization of Feit–Thompson conjecture, for square-free integers

Few weeks ago I wondered about if the following conjecture is in the literature or well if it is possible to find a counterexample. I evoke a generalization of a well-known conjecture, I mean the Feit–...
1
vote
0answers
47 views

If $p^k m^2$ is an odd perfect number with special prime $p$, then what is wrong about the following factor chain approach to proving $p \neq 5$?

Suppose that $n = p^k m^2$ is an odd perfect number with special prime $p$ satisfying $p \equiv k \equiv 1 \pmod 4$ and $\gcd(p,m)=1$. That $n$ is perfect essentially means that $$\sigma(p^k)\sigma(m^...
0
votes
2answers
57 views

Let $n\in \mathbb{Z}^+ $ s.t $n$ has no square factors other than 1. Prove that for any $x \in \mathbb{Z}$, $n|x^2 \implies n|x$ [duplicate]

I tried to prove above theorem. I used the Theorem: Let p be a prime number. Then for any $a,b \in \mathbb{Z}; p|ab \implies p|a$ or $p|b$. Proof: Since $n|x^2$, $x^2 = an$. By prime factorization, $...
0
votes
3answers
41 views

Find all $n$ for which $19 \mid 10^n - 1$

For what values of $n$ (positive integer) does 19 divide $10^n-1$ evenly? The question arises in my fooling around with $2$-parasitic numbers. And I know this is true for $n = 18, 36, 54$ (by ...
-3
votes
1answer
49 views

Calculate $7^{154} \pmod{341}$ [duplicate]

how to calculate remainder of $7^ {154}$ when it is divided by $341$. Could you please state which method or theorem to use.
1
vote
0answers
56 views

When does $120$ divide $n^5 - n$ [duplicate]

For which $n, 120\mid n^5-n$ is true? I could show that $30\mid n^5-n$ is always true by following way: $n^5-n = (n-1)n(n+1)(n^2+1)$ Since the product of three consecutive integers is a factor of $...
1
vote
2answers
107 views

If a prime and its square both divide a number n, prove that $n=a^2 b^3$

Lets call a number $n$ a fortified number if $n>0$ and for every prime number $p$, if $p|n$ then $p^2|n$. Given a fortified number, prove that there exists $a,b$ such that $n=a^2b^3$. I know that ...
1
vote
1answer
23 views

If $p \ge 5$ is prime prove that $\sum_{i=1}^{p-2}\sum_{j=i+1}^{p-1} ij$ is divisible by $p$

If $p \ge 5$ is prime prove that $$\sum_{i=1}^{p-2}\sum_{j=i+1}^{p-1}ij$$ Attempt. We have $$\sum_{i=1}^{p-2}\sum_{j=i+1}^{p-1}ij = \sum_{i=1}^{p-2}i \left[ \frac{(p-1)p - i(i+1)}{2}\right] = \frac{(...