Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [divisibility]

This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.

0
votes
1answer
28 views

Prove that, for all $n\in{Z}$, if $3\mid{n}$ or $18\mid{n-7}$, then there exists $m\in{Z}$ such that $(n^2-9m)(n-9m+2)=0$.

Prove that, for all $n\in{Z}$, if $3\mid{n}$ or $18\mid{n-7}$, then there exists $m\in{Z}$ such that $(n^2-9m)(n-9m+2)=0$. I tried splitting this up into two cases, one where $3\mid{n}$ in which case ...
0
votes
2answers
32 views

What does it mean to not divide any term

I am trying to solve the below problem(Please don't solve it) The sequence 1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201 ... is defined by T1 = T2 = T3 = 1 and Tn = Tn-1 + Tn-2 + Tn-3. ...
2
votes
3answers
53 views

Prove $n=m^3-3m^2+2m$, for any integer $m$, then $n$ is a multiple of $6$.

Prove $n=m^3-3m^2+2m$, for any integer $m$, then $n$ is a multiple of $6$. So far I have that $n=m(m-3)(m+3)$, which are $3$ consecutive integers so at least one must be a multiple of 2. I am not ...
1
vote
1answer
60 views

Divisibility by 2019 [duplicate]

Prove that there exist natural number m which consists digit of only 1, that is divisable by 2019. Generalizations, prove that for any natural numer k there exist natural number n which consists ...
1
vote
3answers
60 views

Find the smallest prime number $p$ such that $p\, | \,n^2-n-2023$ for some integer $n$.

Find the smallest prime number $p$ such that $p\, | \,n^2-n-2023$ for some integer $n$. since $n^2-n =n(n-1)$ is the product of two consecutive integers they must be even so the difference between an ...
1
vote
0answers
23 views

Determine the quotient and the remainder of the division:

Determine the quotient and the remainder of the division: ($1$).of $f\in \mathbb K[x]$ by $x^2-a$ in $\mathbb K[x],$Where $\mathbb K$ is a field. ($2$).of $x^m-1$ by $x^n-1$ in $\mathbb Z[...
-2
votes
1answer
78 views

Finding Remainders [on hold]

What is the remainder when you divide $2018^{2017^{16037838}}$ by $1001$, I’ve reduced the $2018$ to $16$ by taking it $\bmod 1001$ but I can seem to reduce the other powers to a single integer that ...
0
votes
3answers
45 views

$\forall{x}\in\mathbb{Z}$, if $\forall{x}\in\mathbb{N}$, $a^x\mid{x}$, then $a=1$ or $a=-1$.

Prove or disprove: $\forall{x}\in\mathbb{Z}$, if $\forall{x}\in\mathbb{N}$, $a^x\mid{x}$, then $a=1$ or $a=-1$. I tried proving the positive but I'm not sure if it is the right approach.
1
vote
3answers
54 views

Prove that if $a\mid(b-1)$ and $a^2\mid(b^2-2b+4)$, then $a\mid12$.

Prove that if $a\mid(b-1)$ and $a^2\mid(b^2-2b+4)$, then $a\mid12$. I am not sure where to start for this question, any help would be greatly appreciated, thanks!
5
votes
1answer
84 views

Find all $n$ such that $n/d(n) = p$, a prime, where $d(n)$ is the number of positive divisors of $n$

Let $d(n)$ denote the number of positive divisors of $n$. Find all $n$ such that $n/d(n) = p$, a prime. I tried this, but only I could get two solutions. I proceeded like this - Suppose $$n = p^r \...
0
votes
1answer
32 views

Find all 3-digit numbers divisible by a sum of groups of its digits

How to find all three-digit number which are divisible by a sum of specific digit groups explained below? The original number should have only non-zero and non-repeating digits. example: $301$ has a ...
4
votes
3answers
299 views

Find all three digit numbers which are divisible by groups of its digits [on hold]

How can I find all three-digit numbers which: Do not contain a $0$ digit Have different digits Are divisible by below described groups of its own digits The number passing first two conditions ...
0
votes
0answers
15 views

Differences between factoring an equation and dividing one

I've been browsing the Math exchange for some time (as well as other sites) looking for an answer in regards to: "Are there any fundamental differences between factoring an equation, and dividing one?...
0
votes
4answers
44 views

Check divisibility by using $\gcd$.

Let $k$ be an odd integer. As a part of an introductory class to proofs, I wanted to show that the number $k^2 - 1$ is divisible by $8$, and managed to do this by checking that it is congruent modulo $...
3
votes
5answers
80 views

Prove for any positive integer $n$, $(4n)!$ is divisible by $2^{3n}\cdot 3^n$

Problem: Prove for any positive integer $n$, $(4n)!$ is divisible by $2^{3n}\cdot 3^n$ Solution given by the professor: $$4! = 2^3\cdot 3$$ $$(4!)^n = 2^{3n}\cdot 3^n$$ $$\frac{(4n)!}{(4!)^n}=\frac{(...
0
votes
1answer
22 views

Find numbers with n-divisors in a given range

I'm trying to answer this question. Are there positive integers $\le200$ which have exactly 13 positive divisors? What about 14 divisors? If yes, write them. If no, explain why not. Because I'm ...
0
votes
0answers
41 views

If $a\mid b$, then $\forall x(b\in \mathbb z) \exists y(a \in \mathbb Z/a\mathbb Z([x]b\subseteq [y]a.$

I've got a question on how to prove the following statement: If $a\mid b$, then $\forall \big([x]_b\in \mathbb Z, \exists ([y]_a \in \mathbb Z,([x]_b\subseteq [y]_a)\big).$ If additionally, $...
1
vote
1answer
20 views

If $c | m_i$ Prove that $c| \sum_{i=1}^r u_i m_i$ where $m_i,u_i,c \in \mathbb{Z}$ and $i=1,2,..,r$

Let $m_1,m_1,...,m_r,u_1,u_2,...,u_r,c \in \mathbb{Z}$, such that $c | m_i$ for each $i \in \lbrace 1,2,...,r \rbrace$. Prove that $c| \sum_{i=1}^r u_i m_i$ My attempt: We have $c | m_i$ for ...
0
votes
1answer
44 views

Elementary Number Theory Divisibility Question

Let $a, b, c \in \mathbb Z$. I know that if $c|a$ and $c|b$, then $c|a \pm b$. I was working on some elementary number theory and I began to wonder if the following were true:$$\text{if }c|a \text{ ...
0
votes
2answers
16 views

If $\sigma(n) = 2n - d$ and $d \mid n$, is it true that $d = \gcd(n,\sigma(n))$?

In what follows, assume that $d > 0$. Let $$\sigma(x)=\sum_{e \mid x}{e}$$ denote the classical sum-of-divisors function, and denote the deficiency of $x \in \mathbb{N}$ by $$D(x)=2x-\sigma(x).$$ ...
6
votes
1answer
131 views

Patterns in division graphs modulo $n$

(I made an edit due to hints from Alex Ravsky. Thanks to him.) General division graphs with nodes $1,2,\dots N$ and an edge between $n$ and $m$ when $n$ divides $m$ or $m$ divides $n$ are sparse and ...
3
votes
0answers
63 views

Each Player Removes a Number and All Its Divisors

Initially, the numbers $2,3,\ldots,n$ are written on a board. Alice and Bob alternately do the following: erase one number and all its divisors remaining on the board. The player who erases the last ...
23
votes
2answers
230 views

An enigmatic pattern in division graphs

Draw the numbers $1,2,\dots,N$ on a circle and draw a line from $n$ to $m>n$ when $n$ divides $m$: For larger $N$ some kind of stable structure emerges which remains perfectly in place for ever ...
1
vote
4answers
81 views

Prove that $3^{2n} +7$ is divisible by 8

Prove by induction that $3^{2n} +7$ is divisible by 8 for $n \in \Bbb N$ So I think I have completed this proof but it doesn't seem very thorough to me - is my proof valid? If $n=1$ then $3^{2n} ...
1
vote
2answers
48 views

Check if $k$ is divisible by $2^9$ or $2^{10}$

$k=\frac{512!}{256!*128!*...*2!*1! } $ I need to check if the expression k is divisible by $2^9$ or $2^{10}$. This is a multiple choice question and the options and the question goes like this: ...
0
votes
2answers
88 views

Prove that $k^2+k+1$ is not divisible by $101$ for any natural $k.$ [closed]

Prove that $k^2+k+1$ is not divisible by $101$ for any natural $k.$
0
votes
0answers
27 views

Find the natural number which is divisibled by another number

Let $n= \overline{a_1a_2a_3}$ ($a_1 \neq a_2$, $a_2 \neq a_3$, $a_3 \neq a_1$). 1/ How many possible values does $n$ have which is divisibled by $7$? 2/ How many possible values does $n$ have which ...
4
votes
2answers
71 views

For which $p$ primes is $p^{p-1}$ a divisor of $(p-1)^p + 1$?

$p = 2$ and $p = 3$ definitely are solutions. I think these are all the solutions, but how can I prove it?
2
votes
1answer
56 views

Name for this Algorithm

I've managed to prove a bunch of properties about this algorithm that I came up with. I'm now curious to know it's name to see what other people have done. Given a number in base b $$N_0 = b N_X + ...
0
votes
0answers
17 views

Divisibility of $A(x,y)u(x)+B(x,y)v(x)$ by $y$

Let $k$ be a field of characteristic zero, $A=A(x,y),B=B(x,y) \in k[x,y]$, $u=u(x), v=v(x) \in k[x]$. Assume that: At least one of $\{u,v\}$ has degree $\geq 1$. $u$ and $v$ do not have common roots. ...
2
votes
3answers
71 views

Proving prime divisibility relation between $a^2-a+3$ and $b^2-b+25$.

Let $p$ be a given prime number. Prove that there exists an integer $a$ such that $p|a^2-a+3$ if and only if there exists an integer $b$ such that $p|b^2-b+25$. I've managed to prove that if $p|a^2-...
1
vote
0answers
53 views

Division in $\mathbb Z[i]$ of $3+8i$ and $4+i$.

Let $a=3+8i$ and $b=4+i$. We have that $$\frac{a}{b}=\frac{20}{17}+\frac{29}{17}i.$$ So $a=b(1+2i)+1-i$ or $a=b(1+i)+3i$. In both case we have that $N(b)=17$ and $N(1-i)=2<N(b)$ and $N(3i)=9<N(...
2
votes
4answers
47 views

Prove that $\text{gcd}(a, p) = 1 \implies p\nmid a $ is true.

This is one direction of the biconditional in part b of this proposition: Prove that for every prime, $p$, and for all natural numbers $a$, (a) $\text{gcd}(a,p)=p$ iff $p\mid a$ (b) $\text{gcd}(a,p)=...
0
votes
2answers
74 views

Let $p\gt 3$ be an prime. If $\sum_{k=1}^{p-1} \frac{1}{k}=\frac{a}{b}$, where $\gcd(a,b)=1$. Prove that $p\mid a$. [duplicate]

Let $p\gt 3$ be an prime. Suppose $$\sum_{k=1}^{p-1} \frac{1}{k}=\frac{a}{b}$$ where $gcd(a,b)=1$. Prove that $a$ is divisible by $p$. Please give me some hint. Sorry for this types of writing. I am ...
6
votes
4answers
112 views

Factors in a different base $\ 2b^2\!+\!9b\!+\!7\,\mid\, 7b^2\!+\!9b\!+\!2$

Two numbers $297_B$ and $792_B$, belong to base $B$ number system. If the first number is a factor of the second number, then what is the value of $B$? Solution: But base cannot be negative. Could ...
4
votes
1answer
43 views

In what kind of rings a divisor of a product is a product of divisors?

In a unique factorisation domain, if $a|bc$, then $a$ can be written as $a = a_1a_2$ so that $a_1|b$ and $a_2|c$. Is this property of a commutative ring strictly weaker than the property of being a ...
1
vote
1answer
52 views

Probability for composite $n$ to have prime factor $\geq \sqrt n$

Let $\operatorname{GPF}(n)$ denote the largest prime factor of $n\in\mathbb N_{>1}$. My computer tests for intervalls $[m,n]$, where $n<10,000,000$, suggests that the probability $\operatorname{...
2
votes
3answers
167 views

Proof of polynomial divisibility without using complex numbers?

My question is the same as polynomial of degree n and its divisor except I want a solution that does not make use of complex numbers Problem: Find all positive integers $n$ such that $x^2+x+1\mid (...
-2
votes
1answer
57 views

Fibonacci numbers. how to prove? [duplicate]

We are give Fibonacci numbers.{fi | i ∈ N}, where f0 = 0, f1 = 1, fn+2 = fn +fn+1, n∈ N. How to proof with mathematical induction that if n divides by m, then fn divides by fm? I am having trouble ...
0
votes
2answers
81 views

Integer solutions to $x^2(y-1)+y^2(x-1)=1$ [duplicate]

Find all values of $(x,y)$ where $x,y$ belongs to integers if: $$x^2(y-1)+y^2(x-1)=1$$ I m a beginner so I do need some help.
0
votes
2answers
32 views

Proving expressions mod 13

Bob thinks of integer pairs $(a,b)$ such that $a^2+b^2\equiv 0\pmod {13}$ He notices that, curiously, for every pair, at least one of $2a+3b$ or $3b+2a$ is divisible by $13$. I did a similar problem ...
0
votes
2answers
59 views

Prove that $n^{n-1} - 1$ is divisible by $(n-1)^2$ [duplicate]

I am trying to solve the following question: For each positive integer $n$, strictly larger than 1, it holds that $n^{n-1}-1$ is divisible by $(n-1)^2$. This question appears in a chapter on the ...
-1
votes
1answer
26 views

Divide money and things equally between room mates [closed]

My friend and I spent 12730₹ in total to buy some house hold things(say some 10 items). We shared and paid equally. Now we are vacating so we have to divide the items, but my friend wants only 2 items ...
0
votes
2answers
48 views

Is this proposition about polynomials obvious or not? [duplicate]

I am reading an algebra book now. Let $p(x) \in \mathbb{R}[x]$ and $\deg p = n$. Let $\alpha \in \mathbb{C} - \mathbb{R}$ and $p(\alpha) = 0$. Then, $p(\bar{\alpha}) = \overline{p(\alpha)...
0
votes
1answer
34 views

Need help understanding a step in an induction proof

I want to prove that $(n!)^{(n-1)!}$ divides $ n!!$ via induction. I was going through a post I found on Quora doing this, but I got hung up on the last step. For the sake of legibility I'll rewrite ...
0
votes
3answers
59 views

If $p \geq 11$ is a prime then either $p^3-1$ or $p^3+1$ is divisible by $14$

True or False: If $p$ is a prime greater than or equal to $ 11$, then either $p^3-1$ or $p^3+1$ is divisible by $14$ My try The statement is true. In order to prove this, we prove either $$p^3\...
3
votes
0answers
54 views

About the prime divisor of a quadratic function

Encountered in Modell's book Diophantine Equations. In the second chapter, page 3, it says: 'every prime divisor of $p$ of $x^2-a$ for integer $x$ is either a divisor of $a$, or can be represented ...
0
votes
0answers
72 views

show that $(1^p)^k+(2^p)^k+\cdots+((p-1)^p)^k$ is divisible by $p$

This will be reduced to $1^k+2^k+3^k+\cdots+(p-1)^k$ by Fermat Theorem. I know that the sum of the reduced residue system of $n$ is divisible by $n$. What I need to show, though, is that $1^k+2^k+3^k+\...
3
votes
3answers
108 views

Divisor of $x^2+x+1$ can be square number?

$$1^2+1+1=3$$ $$2^2+2+1=7$$ $$8^2+8+1=73$$ $$10^2+10+1=111=3\cdot37$$ There is no divisor which is square number. Is it just coincidence? Or can be proved? *I'm not english user, so my grammer might ...
2
votes
3answers
47 views

Checking the proof of: find all primes $p$ such that $p^2\mid 5^{p^2} +1$

Find all primes $p$ such that $$p^2 \mid 5^{p^2} +1$$ Okay, so I got this: $x = 5^{p^2} +1 = (5^p)^p +1$. In order to use Eulers theorem, I checked that $(5^p, p^2) = 1$, which is true when $p \ne 5$...