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

learn more… | top users | synonyms (1)

0
votes
1answer
15 views

What is the condition for the third variable (divisibility)?

If: $$5 | x + y + z$$ Meaning, 5 divides $x+y+z$ Where $x,y, z$ are integers. They said, if $x, y$ are ARBITRARY there are only two possibilities for $z$? How to do this type of problem?
5
votes
5answers
75 views

Proving that $7^n(3n+1)-1$ is divisible by 9

I'm trying to prove the above result for all $n\geq1$ but after substituting in the inductive hypothesis, I end up with a result that is not quite obviously divisible by 9. Usually with these ...
0
votes
0answers
22 views

Less-ugly proof of infinitude of primes of form 6N+1

While reviewing a free online algebra text I came across this problem in the sort of remedial section of the book: Prove that there are an infinite number of primes of the form $6n + 1$. I had a ...
2
votes
2answers
26 views

Simple Division Proof

Prove that for every three integers i, j, and k, if i $\nmid$ jk, then i $\nmid$ j We've just started proofs and I am at a complete loss for how to go about doing it. I've tried proving through ...
1
vote
3answers
58 views

Prove $4|10^n \iff n>1$

I am just wondering if it is true that $4|10^n \iff n>1$. I was thinking that it is because $2|10$ and $2\cdot2=4$ so $4|10^2$ but not $10$ so $n > 1$.
2
votes
3answers
169 views

Polynomial division challenge

Let $x,y,n \in \mathbb{Z} \geq 3$, Find $A,B$ such that $$x^{n-1}+x^{n-2}y+x^{n-3}y^2+\cdots+x^2y^{n-3}+xy^{n-2}+y^{n-1}= A(x^2+xy+y^2)+B$$ What is the best method to approach this?
2
votes
2answers
34 views

Connection between GCD and totient function

I found the following formula which connects Euler's totient function with gcd at wikipedia. $$ \gcd(a,b) = \sum_{k|a \; \hbox{and} \; k|b} \varphi(k). $$ The problem is that I can not figure out ...
2
votes
5answers
87 views

Show that $2222^{5555} + 5555^{2222}$ is divisible by $ 7$ [duplicate]

Show that $2222^ {5555} + 5555 ^ {2222}$ is divisible by $7$. I tried factorizing but it didnt lead to anything. Can divisibility rules be used? Any ideas please tell me.
1
vote
1answer
42 views

Prove that 100…500…1 (100 zeros in each group) is not a perfect cube?

How can i prove that 100...500...1 [100 zeros in each group ( ... is 100 zeros)]is not a perfect cube? I tried symmetric features of the number but could not figure out anything related.any ideas ...
2
votes
2answers
33 views

Divisibility of three polynomial terms

So here is the statement that im having trouble proving: If $9\mid x^3+y^3+z^3$ then $3\mid xyz$ for integers $x,y,z$. I tried applying the definition of divisibility but that doesn't seem to ...
0
votes
0answers
36 views

Most general GCD (commutative) ring

I'd like to know much about GCD in general commutative rings. Do you have books, sites or articles to recommend ? There is a lot to read about GCD in integral domain, but almost nothing in ...
7
votes
3answers
294 views

Invert and subtract, is there any explanation?

I see in many Brazilian sites that, if you get a number and subtract it by its reverse, you will have zero or a multiple of nine. For example: ...
3
votes
2answers
88 views

Divisors of $2^{2^{127}-1}-1$

Consider the recursively defined number sequence $f(0) = 2$ $f(n+1) = 2^{f(n)}-1$ This sequence goes like $2$, $3$, $7$, $127$, $2^{127}-1$, $2^{2^{127}-1}-1$, $\ldots$. Facts: $2$, $3$, ...
1
vote
5answers
86 views

Prove that $n^3+2$ is not divisible by $9$ for any integer $n$

How to prove that $n^3+2$ is not divisible by $9$?
-1
votes
3answers
42 views

Prove that $\forall n \in \mathbb Z,\;n^2 + 1$ is not divisible by $3$ [on hold]

"Prove that $n^2+1$ is not divisible by $3$ for any integer n." How to prove this?
0
votes
2answers
66 views

Prove: p-mq | f(m) where 'm' is any integer

How to prove that $p-mq \mid f(m)$ where $m$ is any integer, $f(x) = A_0 + A_1 x + A_2 x^2 + ... + A_{n-1} x^{n-1} + A_n x^n$, $f(x)∈ ℤ[x]$, $p/q$ is a zero for $f(x)$ and $p$ and $q$ are coprime ...
3
votes
2answers
54 views

Proper divisors of 1?

What are the proper divisors of 1? I understand proper divisors do not include the number itself, but is 1 an exception or does it have no proper divisors?
7
votes
4answers
93 views

Show $17$ does not divide $5n^2 + 15$ for any integer $n$

Claim: $17$ does not divide $5n^2 + 15$ for any integer $n$. Is there a way to do this aside from exhaustively considering $n \equiv 0$, $n \equiv 1 , \ldots, n \equiv 16 \pmod{17}$ and showing $5n^2 ...
1
vote
1answer
47 views

Finding the inverse modulo . $7^{-2}\pmod {11}$ and $7^{-3}\pmod {11}$

$7^{-1}\pmod{11}$ the above can be found by $7x\pmod{11}\equiv 1$ and $x=8$ now i am confused on how to find $7^{-2}\pmod{11}$ and $7^{-3}\pmod{11}$ .
1
vote
2answers
46 views

Show that for every $n > 1$ there exist $n$ consecutive composite numbers [duplicate]

So I am trying to prove that for every $n > 1$ there exist $n$ consecutive composite numbers but I do not know even how to start. This is a problem in analytic number theory. Please can you help ...
2
votes
2answers
19 views

proof : $a,b \in N, a^5 | b^5 \rightarrow a | b$

I couldn't find anything to use apart from the fundamental theorem of arithmetic. Here is my proof : Let $a,b \in N$ Suppose $a^5 | b^5$ Let $S = \{ \text{ n is prime } , n | a \lor n | b \} $ $ ...
3
votes
3answers
90 views

How can I demonstrate that $x-x^9$ is divisible by 30?

How can I demonstrate that $x-x^9$ is divisible by $30$ whenever $x$ is an integer? I know that $$x-x^9=x(1-x^8)=x(1-x^4)(1+x^4)=x(1-x^2)(1+x^2)(1+x^4)$$ but I don't know how to demonstrate that ...
-1
votes
0answers
26 views

Number theory equation with greatest common divisor. [closed]

We have the three following equations: $n + k = (\gcd(n,k))^2$ $k + m = (\gcd(k,m))^2$ $m + n = (\gcd(m,n))^2$ Solve the eqaution, where $k,n,m$ ...
1
vote
5answers
51 views

Show $\nexists k:3^7\mid k!$ but $3^8\nmid k!$

Show $\nexists k:3^7\mid k!$ but $3^8\nmid k!$ Ideas: I need to find integer $m$ such that $m=\frac{k!}{3^7}$ and $m\neq\frac{k!}{3^8}$, but I have 2 unknowns so don't know how to proceed from here. ...
1
vote
1answer
21 views

Division rules for other number systems?

How could we make the same division rules for other number systems, like in our decimal system: a number is divisible with 2 if it's last digit is 0,2,4,6,8, by 3 if the sum of digits is divisible ...
0
votes
1answer
24 views

$\operatorname{lcm}(a,b) = c$ and $\gcd(a,b) = d$ => $\operatorname{lcm}(\frac{a}{d},\frac{b}{d}) = \frac{c}{d}$ in a Euclidean domain or PID

I know that in an integral domain $c=\operatorname{lcm}(a,b)$ if and only if $a\mid c, b\mid c$ and if there exists $c'$ such that $a\mid c', b\mid c'$ then this implies that $c\mid c'$. And ...
4
votes
1answer
57 views

Finding missing digits in factorials

14!=871a82b1200 without working out 14!, find a and b I think it has something to do with maths rules regarding 9 or 3 (the digits adding up to either of those numbers) but not entirely sure!
1
vote
0answers
16 views

What is a distributed lattice has to do with GCD and LCM?

I am lost while following this explanation: Let $$A(g, i) = gcd(F_{g}, lcm(F_{a_{1}}, F_{a_{2}}, ... , F_{a_{i}}))$$ and $$X = lcm(F_{a_{1}}, F_{a_{2}}, ... , F_{a_{i - 1}})$$ Then $A(g, i) = ...
1
vote
1answer
30 views

Divisibility problem using Wilson's theorem: $4(p-3)! + 2$ is divisible by $p$

Prove that $4(p-3)! + 2$ is divisible by $p$, where $p$ is an odd prime. Use Wilson's theorem. I am having trouble trying to bring it in the form where Wilson's theorem can be applied. Any help ...
0
votes
0answers
37 views

Put this word problem into math terms: A man goes to a stream…

A man goes to a stream with an 18-pint container and a 26-pint container. Using only these two containers: a) How does he get 2 pints of water into the larger container? b) What are all the ...
2
votes
1answer
16 views

Prove that for positive integers a, b, c, and d such that b != d, if gcd(a, b) = gcd(c, d) = 1 then a/b + c/d is not an integer. [duplicate]

I attempted this by assuming that a/b + c/d is an integer and coming to a contradiction, but I got stuck. Any hints?
1
vote
0answers
51 views

$A,B \in M(n,\mathbb R)$ such that $A^2+B^2=AB$ and $AB-BA$ is invertible ; $n$ is divisible by $3$? [closed]

Let $A,B \in M(n,\mathbb R)$ such that $A^2+B^2=AB$ and $AB-BA$ is invertible , is it true that $n$ is a multiple of $3$ ?
6
votes
4answers
132 views

Efficiently producing certain kinds of examples of the application of Euclid's algorithm

Is there some efficient way to churn out pairs of integers $n,m$ such that $\gcd(n,m)=1$; $n,m$ both have fairly large numbers of fairly small prime factors; and Euclid's algorithm applied to $n,m$ ...
2
votes
9answers
82 views

Prove that if $a, b$ are any positive integers $>1$, then either $a$ or $b$ or $a+b$ or $a-b$ is divisible by 3.

I checked all the integers from $1$ to $1000$ manually, I don't know exactly how to prove this but any simple and easy proof would be appreciated. Thanks.
0
votes
1answer
57 views

Arithmetic mean 6 times greater than GCD?

I am not sure how to find an answer to this question. Is there a way to solve it without simply trial and error? Do there exist ten distinct positive integers such that their arithmetic mean is (a) ...
3
votes
2answers
63 views

GCD of many numbers

Given $a_1,...,a_n$ $gcd(a_1,...,a_n) = b$ I need to find $i$, so if i apply euclids algorithm to $(a_1,a_i)$, i end with $(0,b)$ or $(b,0)$.
2
votes
4answers
50 views

How does one show that for $k \in \mathbb{Z_+},3\mid2^{2^k} +5$ and $7\mid2^{2^k} + 3, \forall \space k$ odd.

For $k \in \mathbb{Z_+},3\mid2^{2^k} +5$ and $7\mid2^{2^k} + 3, \forall \space k$ odd. Firstly, $k \geq 1$ I can see induction is the best idea: Show for $k=1$: $2^{2^1} + 5 = 9 , 2^{2^1} + ...
0
votes
2answers
50 views

Why doesn't x/0 = ±∞ [duplicate]

I was watching a video on numberphile about dividing by 0 and It said that x/0=Undefined or Error since it could be + or - ∞. ...
1
vote
2answers
20 views

Proof dealing with greatest common divisors

I'm working on a proof which concludes that if $a\equiv b (mod\ m)$ then $gcd(a,m) = gcd(b,m)$ I know that we can rewrite the congruence as $km = a-b$ for some $k \in \mathbb{Z}$ I rearranged the ...
1
vote
3answers
71 views

Prove for positive integers a,b,c and d (where b does not equal d), if gcd(a,b) = gcd(c,d) = 1, then a/b + c/d is not an integer

I understand that if gcd(a,b) and gcd(c,d) = 1, at least one number in each pair is a prime or is 1. As for after that, I'm totally stumped, could I get some tips, clues, help?
1
vote
3answers
32 views

Prove for integers a, b, and c, if gcd(a, b) = 1, a|c, and b|c then ab|c

Prove for integers $a$, $b$, and $c$, if $\gcd(a, b) = 1$, $a|c$, and $b|c$ then $ab|c$. Part b of this question is: "Is the converse true? Prove or disprove accordingly?" Hey, so I've been drawing ...
3
votes
4answers
80 views

If gcd$(a,b) = 1$, then I want to prove that $\forall c \in \mathbb{Z}$, $ax + by = c$ has a solution in integers $x$ and $y$.

If gcd$(a,b) = 1$, then I want to prove that $\forall c \in \mathbb{Z}$, $ax + by = c$ has a solution in integers $x$ and $y$. This is what I was attempting or trying: Let $d =$ gcd$(a,b)$. $d|a ...
0
votes
0answers
18 views

GCD and fraction problem

If x/y = 1/a + 1/b + 1/c and GCD of a , b and c is 9 then find a) minimum of x and y which do not cause x/y repeating decimal b) the best of x and y that cause x/y nearly to 3/10 many ...
2
votes
2answers
44 views

Find all numbers of form $10^k+1$ divisible by $49$

Basically, I've tried to take mods, and it hasn't been very successful. Also, if it helps, I noticed that the sequence can be recursively written as $a_{n+1}=10a_n-9$, starting with $a_1=11$.
0
votes
0answers
29 views

Determine when a prime divides this

Let $x$ and $y$ be integers, and consider the expressions $A=192x+a$ and $B=192y+b$, where $a,b$ are nonnegative mod $192$ residues (so $a,b\in \{0,1,2,...,191\}$). For which ordered pairs $(a,b)$ ...
0
votes
1answer
50 views

Principal Ideal Ring and ID

In definition of PID, if we take ring instead of ID call it PIR. I add one more condition: all generators of an ideal are associate to each other. Would it imply PIR with this condition is PID? ...
0
votes
1answer
64 views

prime implies irreducible

In unique factorization ring with unity(I am not considering commutativity and zero divisor in definition of UFD) irreducible implies prime. And it was proved in ring with unity without zero ...
3
votes
2answers
27 views

What is sum of totatives of n(natural numbers $ \lt n$ coprime to $n$ )?

Same question as in title: What is sum of natural numbers that are coprime to $n$ and are $ \lt n$ ? I know how to count number of them using Euler's function, but how to calculate sum?
0
votes
1answer
47 views

UFD, prime and Irreducible

I am taking following definitions and calling algebraic structure U1 and U2 definition as: U1 is A ring R with unity and properties properties Every element of R is neither 0 nor a unit can be ...
0
votes
1answer
76 views

Prime element in ring without unity

Definitions of prime element: $(1)$ We say $p$ is prime if $p|ab$ it implies $p|a$ or $p|b$ (I don't need definition of unity here) $(2)$ We say $p$ is prime if $p=ab$ it implies $p|a$ or $p|b$ (I ...