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
-1 votes
1 answer
51 views

Approaching a Divisibility Question

Perhaps I'm a bit rusty on my number theory, but I have been struggling to figure out how to determine what positive integers $x$ and $y$ satisfy $$ x+y \text{ divides } x^2 + y^2 $$ Any thoughts? I ...
Manuel Guillen's user avatar
1 vote
0 answers
39 views

$(a^m+b^m)\mid(a^n+b^n) \iff m\mid n$ [duplicate]

Prove that $(a^m+b^m)\mid(a^n+b^n) \iff m\mid n$. Here $a, b, m, n\in\mathbb{Z}^+$, $m\leq n$ and $(a, b)=1$. This is a questions from a number theory book that I am recently studying. I have read ...
IraeVid's user avatar
  • 2,920
1 vote
1 answer
52 views

How to logically represent a smaller number being divided by a large number on a number line?

Recently I asked this question on this platform: When we divide a number by another number ($x \div y$), we can interpret it in two ways: $x$ is divided in equal groups, where each group consists of $...
Steve's user avatar
  • 73
-4 votes
0 answers
53 views

Find the values of integers A and N (≥A) for which (3ᴬ - 2ᴬ)/(2ᴺ - 3ᴬ) is a positive integer

Is there any way to find the values of integers A and N (≥A) for which (3ᴬ - 2ᴬ)/(2ᴺ - 3ᴬ) is a positive integer? I'm trying to disprove the Collatz Conjecture: ...
WeCanDoItGuys's user avatar
3 votes
0 answers
110 views

How many 7-digit numbers with distinct digits can be made that are divisible by 3?

How many 7-digit numbers with distinct digits can be made that are divisible by 3? First of all, I counted all the ways to insert 7 of 10 digits in a number making the number divisible by 3. Digits ...
RobStam's user avatar
  • 31
-3 votes
0 answers
47 views

Prove that $n^7-n$ is divisible by $42$ [duplicate]

Prove that $n^7-n$ is divisible by $42$ for all $n$. I have proven one part using induction, but how do I prove the other one?
Calculas's user avatar
2 votes
1 answer
117 views

Prove The Divisibility rule of 19 [duplicate]

I'm a beginner in number theory, I was trying to prove the divisibility rule of 19, can someone help me to complete my proof Let $n$ be $10a + b$ where b is the unit digit and 10a is the rest; 10 is ...
BGOPC's user avatar
  • 147
-3 votes
1 answer
84 views

Can someone simplify this maths question for my tiny brain to understand? [closed]

My maths teacher gave me this question, but i have no clue what it means: The nine numbers $p_1,p_2 ... ,p_9$ are distinct primes. $N$ positive integers are chosen, where $N$ is a multiple of 100, so ...
Chromegism's user avatar
4 votes
1 answer
140 views

BMO1 number theory question on fibonacci sequence and divisibility

This is question 2 from the 1983 British Maths Olympaid The fibonacci sequence $f_{n}$ is defined by $f_{1} = 1, f_{2} = 1,$ and $f_{n} = f_{n-1} + f_{n-2}, n > 2$ prove that there are integers a,...
Chris Daniel's user avatar
0 votes
5 answers
91 views

How to logically interpret the division of small number by large number on a number line?

When we divide a number by another number ($x \div y$), we can interpret it in two ways: $x$ is divided in equal groups, where each group consists of $y$ $x$ is divided in $y$ equal groups Suppose ...
Steve's user avatar
  • 73
0 votes
2 answers
88 views

How many 6-digit numbers of the form xyzzyx (where y is a prime number) are possible which are divisible by 7?

How many 6-digit numbers of the form $xyzzyx$ (where $y$ is a prime number) are possible which are divisible by 7? My try: Since we were checking for a multiple of 7, I tried using the 7 divisibility ...
Darshit Sharma's user avatar
2 votes
2 answers
95 views

positive integers property

The positive integers are written into rows so that row n includes every integer m with the properties: a) $m$ is a multiple of $n$; b) $m \leq n^2$ ; c) $m$ is not in the earlier row. Determine the ...
user124297's user avatar
1 vote
0 answers
37 views

Commutative ring with an element divisible by all powers of $a$ but with no corresponding infinite sequence

Is there a commutative ring $R$ with two elements $a$ and $b$ for which $b \in \bigcap_{n \ge 0} a^nR$ (the intersection of the principal ideals generated by the powers of $a$), but there is no ...
Geoffrey Trang's user avatar
0 votes
0 answers
41 views

When is (a+b+c)(1/a+1/b+1/c) integer [duplicate]

I was a kind of curious over this for past few days, If $a_1, a_2, a_3$ can be any natural nos, what are the distinct integer values $(a_1+a_2+a_3)(\frac{1}{a_1}+\frac{1}{a_2}+\frac{1}{a_3})$ can ...
Lucid's user avatar
  • 144
1 vote
1 answer
39 views

Can relative (or even absolute) quotient size be calculated from a list of polynomials which are multiples of a given variable?

I am working on a Diophantine equation in integers $x$ and $y$. The equation has been solved, so I already know the solutions (there are four) — I am trying to find a more elementary solution. Through ...
Kieren MacMillan's user avatar
1 vote
0 answers
24 views

Proof of existence in division with remainder [duplicate]

Proposition. Let $a\in \mathbb{Z}^+$, $b\in\mathbb{Z}$. Then there exist unique numbers $q,r\in\mathbb{Z}$ such that $b=qa+r; 0≤r<a.$ Proof. Existence: Define $S:=\{b-qa \mid q\in \mathbb{Z}, b-qa\...
Holland Davis's user avatar
4 votes
1 answer
143 views

Infinitely many $a_n$ [closed]

Let $\{a_n \}$ be a sequence defined as follows: $$ \begin{gathered} a_0=0 ; a_1=1 ; a_2=2 \text { and } \\ a_{n+3}=5^n \cdot a_{n+2}+n^2 \cdot a_{n+1}+11 a_n \text { for } n \geq 0 . \end{gathered} $$...
TheLoneWolf's user avatar
1 vote
1 answer
32 views

Another Binomial Coefficient Congruence Modulo Prime Powers

I have the following conjecture on binomials modulo prime powers: Let $s, b, n \ge 0$ be integers, let $p$ be a prime and let $0\le k_0 < p^{b+1}$ and $0\le n_0 < p^{b+s}$, then we have the ...
Thomas Ahle's user avatar
  • 4,512
1 vote
1 answer
59 views

Find all positive integers m so that for $n=4m (2^m - 1)$, $n | (a^m - 1)$ for all a coprime to n

Find all positive integers m so that for $n=4m (2^m - 1)$, $n | (a^m - 1)$ for all a coprime to n. First, we try $m=1$. Then $n=4$, and clearly it is not true that $4 | (a-1)$ for all odd a. For $m=2,...
Alfred's user avatar
  • 863
0 votes
4 answers
188 views

Formally prove that $3^ {80} - 2^{20}$ divisible by $5$ [duplicate]

I am not sure how to formally prove that prove that $3^{80} - 2^{20}$ divisible by $5$; any hints would be much appreciated. My initial approach was to write a table with examples that when both $3$ ...
the_one_that_day_dreams's user avatar
-1 votes
0 answers
32 views

Show that if n is an odd integer that is not a multiple of 5, then there exists an integer, all of whose digits are 1, that is divisible by n. [duplicate]

For example 7|111111 We have been working with Φ(n) functions but I dont see how these are related
Ryan Streeser's user avatar
4 votes
1 answer
185 views

What is the remainder when dividing $a$ by $5$ if $\sum_{k=1}^{1992}\frac{1}{k}=\frac{a}{b}$?

Consider $$\sum_{k=1}^{1992}\frac{1}{k}=\frac{a}{b}.$$ If $a$ and $b$ are natural numbers that are relatively prime, what is the remainder when dividing $a$ by $5$? $\text{(A) } 0 \space\space\space\...
Hussain-Alqatari's user avatar
0 votes
2 answers
48 views

If primes $p_1 \neq p_2$ divide $n$, then $\exists$ $x, y \in G \setminus \{e\}$ such that $\langle{x}\rangle \cap \langle{y}\rangle = \{e\}$

Q: If $G$ is a group with order $n$, and $p_1$ and $p_2$ are distinct primes that divide $n$, show that there exists $x, y \in G \setminus \{e\}$ such that $\langle{x}\rangle \cap \langle{y}\rangle = \...
user858034's user avatar
0 votes
2 answers
90 views

Find $n$ knowing some divisibilities

Question : Determine the natural numbers $n$, given that $3^n-1$ is divisible by $2^n$, and given that $4^n-1$ is divisible by $3^n$. My Idea : We can say that $4^n \equiv 0 ( \mod 4 )$ , which means ...
IONELA BUCIU's user avatar
-3 votes
1 answer
56 views

For prime $p$, show that $p\mid a^n\Rightarrow p\mid a$ [duplicate]

I already try to solve this with divisibility rule $p = ka, a^n$ = $ka*ka$ as much as $n$ times $a^n≡a (mod n)$, then $p^n=ka*ka$ therefore $p^n= a^n$ be $^n√p^n|^n√a^n$ which $p|a$ but im not sure ...
Rahayu's user avatar
  • 1
3 votes
2 answers
213 views

Solution Verification for RMO (Indian Math Competition)

Let N be the set of all positive integers and $S={(a,b,c,d)\in N^4: a^2+b^2+c^2=d^2}$. Find the largest positive integer m such that m divides abcd for all (a,b,c,d) \in S (RMO Problem 1: 29 Oct, 2023)...
Starlight's user avatar
  • 1,456
1 vote
1 answer
57 views

Do exist positive integers $a < b$ with the following property: Whenever $m, n$ are positive integers with $m^a|n^b$ then $m|n$. [duplicate]

Decide with justification if there exist positive integers $a < b$ with the following property: Whenever $m, n$ are positive integers with $m^a|n^b$ then $m|n$. Here's my attempt at a proof: Assume ...
Eli Witz's user avatar
-1 votes
1 answer
101 views

Prove that if $m^2$ is even then $m$ is even [duplicate]

$m, n \in \mathbb{Z}$ $m^2 = 2n^2 \implies m = 2k$ for some $k \in \mathbb{Z}$ In other words, the first statement implies $m$ is divisible by 2. Why? My professor used this without proving it. My ...
user129393192's user avatar
0 votes
0 answers
33 views

Why do all parasitic numbers seem to be multiples of repunits?

Let $n$ be a number. Take the last digit of $n$ and move it to the front to produce a new number $m$. If $n$ divides into $m$, then we call $n$ a parasitic number (in base 10). For example, $n = ...
Silvio Mayolo's user avatar
2 votes
0 answers
66 views

Formulas that generate "too few" primes

I am looking for examples of formulas $f: \mathbf{N} \rightarrow \mathbf{N}$ for which the number of conjectured primes $p \in \text{ Im}(f)$ is either finite or less than what naive heuristics would ...
Antosha's user avatar
  • 149
-2 votes
1 answer
50 views

Prove that a*b is not divisible by prime number p [duplicate]

Can't understand if my thoughts make sense or not. The question is the following: $ab$ is not divisible by prime $p$, if both $a$ and $b$ are not divisible by $p$. I thought to prove it like this: For ...
uduck's user avatar
  • 1
1 vote
0 answers
51 views

Given $a,b \in \mathbb{N}$, is it true that $\phi(\gcd(a,b))=\gcd(\phi(a),\phi(b))$?

Let $a,b \in \mathbb{N}$ and $d=\gcd(a,b)$. Then we have that $a/d$ and $b/d$ are coprime. I am trying to see if $\phi(a)/\phi(d)$ and $\phi(b)/\phi(d)$ are also coprime ($\phi$ is the Euler totient ...
Luigi Traino's user avatar
0 votes
2 answers
65 views

Find N such that for all x $\ge$ N, $P(x)$ is Divisible by Primes Bigger than 10

Given an arbitrary distinct natural numbers, $d_1, d_2, d_3, d_4,$ and $ d_5$. Let $P(x) = (x + d_1)(x + d_2)(x + d_3)(x + d_4)(x + d_5)$. Prove that there is a number $N$ (in terms of $d_1, d_2, ...$...
FaranAiki's user avatar
  • 296
-1 votes
2 answers
84 views

The exact meaning of $1/0$?

What is the exact meaning of $1/0$? Does that mean a number that is very large, a number that cannot be expressed as the one we know, infinite numbers of number so that giving one particular value is ...
KeSHAW's user avatar
  • 7
4 votes
1 answer
81 views

Prove that there exists a unique partition of $\mathbb{N}$ into A and B so that neither of $A\oplus A$ and $B\oplus B$ has a prime.

For any subset $S\subseteq \mathbb{N}, $ let $S\oplus S = \{a + b : a,b \in S , a\neq b\}$. Prove that there exists a unique partition of $\mathbb{N}$ into disjoint subsets A and B so that neither of $...
user3472's user avatar
  • 1,195
1 vote
0 answers
32 views

Prove that ${n\choose k}$ has at least k distinct prime divisors by proving an intermediate statement first

Let $k\in\mathbb{N}$ and let $L_k = lcm(1,2,\cdots, k)$. Let $n\in\mathbb{N}$ with $n\ge k + L_k$. Prove that ${n\choose k}$ is divisible by $\prod_{i=0}^{k-1} \dfrac{n-i}{\gcd(n-i, L_k)}$ and ...
Alfred's user avatar
  • 863
5 votes
1 answer
116 views

Prove that for all integers $a,b, b\neq 0,$ there exists $n$ with $v_2(n!) \equiv a\mod b$.

Let $v_p(m)$ for a prime p and an integer m be the largest integer d so that $p^d | m$. Prove that for all integers $a$ and $b$ with $b\neq 0,$ there is a positive integer n so that $v_2(n!) \equiv a\...
user3472's user avatar
  • 1,195
0 votes
1 answer
65 views

Show that the number isn't divisible by 341 (using congruences & Fermat's little theorem) [duplicate]

Show that the number $3^{341}-3$ isn't divisible by $341$. We've just covered Fermat's little theorem and linear congruences in my Algebra class. I've realized that $341 = 11*31$ and I've wrote down: $...
runtotherescue's user avatar
2 votes
1 answer
99 views

Find all integers $n>1$ with the property that for each positive divisor $d$ of $n$, we also have that: $(d+2) \mid(n+2) $.

Find all integers $n>1$ with the property that for each positive divisor $d$ of $n$, we also have that: $$ (d+2) \mid(n+2) $$ So far, I've tried to get as much info about it as possible, but I don'...
TheLoneWolf's user avatar
1 vote
1 answer
58 views

Criterion for a factorial ratio to be integral

Let $a_1,a_2,\ldots,a_K,b_1,b_2,\ldots,b_L$ be positive integers. Prove that $$\frac{(a_1n)!(a_2n)!\cdots (a_Kn)!}{(b_1n)!(b_2n)!\cdots (b_Ln)!} $$ is an integer for all positive integers $n$ if and ...
DesmondMiles's user avatar
  • 2,650
0 votes
1 answer
61 views

Pick a, b, c randomly without any conditions from the set ${1, 2, 3,..., 2019}$ What is the probability for $abc + bc + c$ to be divisible by 3?

Note: I revisited this problem after I can mostly understand modular arithmetic. Since I was not too satisfied with those answers I decided to try to answer question once again with my own ...
Hayst's user avatar
  • 165
1 vote
3 answers
83 views

Proving divisibility of a sum $\sum_{k=0}^{\lfloor{n/2}\rfloor} (-1)^{k}\binom{n}{2k} 7^{k}$

I have been given $$ \sum_{k=0}^{\lfloor{n/2}\rfloor} (-1)^{k}\binom{n}{2k} 7^{k} $$. How can I show that it is divisible by $2^{n - 1}$ for any positive integer $n$? I have attempted to write it in ...
Dave Conkers's user avatar
-3 votes
1 answer
61 views

(Dis)prove $\,a\mid b\,\Rightarrow\, a+b\mid b+c$ [duplicate]

Can someone help me here? I'm completed stuck in this simple problem. Let a, b, c $\in \mathbb{N} $, check if the statement below is true or false: if   a|b then (a+b) | (b+c) Any tips? What i've ...
Hesoyam's user avatar
  • 13
0 votes
0 answers
8 views

Proving $n$ divides $φ(a^n − 1)$ for any positive integer $a$ and $n$, where $a^n - 1 > 1$ [duplicate]

How will I be able to show that $n|φ(a^n − 1)$ for any positive integer $a$ and $n$, where $a^n - 1 >1$? I already have an idea that I will probably need to use cyclotomic polynomials. Will I also ...
All is number's user avatar
0 votes
0 answers
36 views

Relation between two functions with divisibility properties

Given a positive integer $q$ and a finite set $A\subseteq \mathbb{N}$, define the functions $$ f(q)=\sum_{k=1}^{\infty}\sum_{\substack{n,m\in A \\ n-m=qk}}1 \quad \mbox{and}\quad g(q)=\sum_{\substack{...
Itachi's user avatar
  • 440
0 votes
1 answer
26 views

Intervals of length $k$ with at least $n$ distinct prime factors

Question: For $k,n\in \mathbb{N}$, what is the smallest $b$ such that there is an interval $N=(b-k,b]\subset \mathbb{N}$ of length $k$ with at least $n$ distinct prime factors dividing the integers $x\...
Tejas Rao's user avatar
  • 1,860
0 votes
0 answers
86 views

A number with digits $2$ and $5$ is divisible by $2^{2005}$ [duplicate]

I found an old problem on a website but no answer is given. Here is the problem : Prove that there is a unique positive integer consisting entirely of digits $2$ and $5$, having exactly $2005$ digits ...
maxime gamelin's user avatar
8 votes
2 answers
147 views

Prove that there are infinitely many pairs $(m, n)$ such that $(m!)^n + (n!)^m + 1$ is divided by $n + m$.

When I saw factorials, I immediately thought about Wilson's theorem. However, I didn't succeed at all. I also thought about cyclic groups, but with such amount of information I haven't find the use of ...
Ferkal1t's user avatar
0 votes
0 answers
27 views

If a number $n$ shares a common factor with $p^{\alpha}$, then $p|n$. [duplicate]

Let $p$ be prime, $n \in \mathbb{Z}$, $\alpha \in \mathbb{Z}^{+}$. Suppose that $n$ shares a common factor with $p$. I wish to conclude that $p|n$. The proof follows: If $p$ is prime, then the factors ...
V. Elizabeth's user avatar
0 votes
1 answer
67 views

Trouble manipulating quotients in $\mathbb{N}^\times$

As part of a proof about multinomial expansions, I am encountering difficulty in showing the following equality: $$\frac{k!}{\alpha!} = \frac{(k-\alpha_1)!}{\alpha'!}\frac{k!}{\alpha_1!(k - \alpha_1)!}...
EE18's user avatar
  • 1,221

1
2 3 4 5
122