Questions tagged [divisibility]
This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.
0
votes
0answers
4 views
Some questions regarding the proof of Luroth theorem given by G. Bergman
G. Bergam gave a series of problems leading to the proof of Luroth's Theorem: https://math.berkeley.edu/~gbergman/grad.hndts/Luroth.ps
My concern lays in problem (7) and (8).
$L$ is any intermediate ...
0
votes
0answers
9 views
Prove $\phi(p^e)\not|p^et-1$
Let p be a prime, m an odd positive integer such that $ p^e||m$, where $ e>1 $ is an integer. I am trying to show that
$$ \phi(p^e)=p^e-p^{e-1}\nmid p^et-1=m-1 $$
Is it enough to just say that ...
0
votes
3answers
45 views
Find the remainder from the division of $3^{2017}-1$ into $3^{403}-1$
Here is an interesting problem:
Find the remainder from the division of $3^{2017}-1$ into $3^{403}-1$
-1
votes
1answer
73 views
Find a $x$ such that $2^{2015}x\equiv 1 \pmod{13}$ [on hold]
Since 13 is prime number using little Fermat's theorem $2^{12}\equiv 1 \pmod {13}$ then $2^{2015}\equiv 2^{12\cdot167+11}\equiv 2^{11} \pmod{13}$ then $2^{2015} x \equiv 2^{11} x \equiv 1 \pmod{13}$ ...
0
votes
0answers
27 views
Prove that $n$ is not divider of number $2^n-1$, if $n>1$ [duplicate]
Prove that $n$ is not divider of number $2^n-1$, if $n>1$
If we think opposite, then $n$ is divider of number $2^{n}-1$, since $2^{n}-1$ is odd number then $n\not=2k$, where $k\in \mathbb Z$, now ...
0
votes
1answer
34 views
How to prove an equivalence of two equations?
Task:
Prove that . $s \cdot a + t \cdot b = c$ has a solution $s, t \in \mathbb{Z}$ iff $c$ is a multiple of $ gcd(a,b) $.
I’m not sure whether my proof is correct or not, so pleas have a look on it:
...
1
vote
1answer
23 views
Checking if the Product of n Integers is Divisible by Prime N
Given $n$ integers, $x_1, ... , x_n$, is there some well-known procedure or algorithm that checks if the product $x_1 * ... * x_n$ is divisible by some arbitrary prime $N$ using minimal space?
Since ...
0
votes
3answers
41 views
Infinite sequence $2^{n}-3 (n=2,3,…)$ contains no term divisible by 65
Show that the infinite sequence $2^{n}-3 (n=2,3,...)$ contains infinitely many terms which are divisible by $5$ and infinitely many terms which are divisible by $13$, but no terms which are divisible ...
1
vote
0answers
31 views
$2^{b}-1$ does not divide $2^{a}+1$
If $a$ and $b>2$ are any positive integers, then prove that $2^{a}+1$ is not divisible by $2^{b}-1$
Here's my attempt:
If $2^{b}-1\mid 2^{a}+1$
then it is obvious that $a>b$.
Now ,By division ...
0
votes
3answers
24 views
proof that the sum of digits of natural number are divisible by 3 iff the number is [duplicate]
Im trying to prove that every natural number is divisble by three if and only if the sum of its digits are divisible by three.
First i proved by induction that $10^n-1$ is divisible by 9 (and ...
-1
votes
0answers
50 views
What Happens to e as x Approaches Infinity? [duplicate]
When we take $(1 + 1/1000000)^{1000000}$ we get $2.71828046916$; all the same, when we take $(1 + 1/1000000000)^{1000000000}$ we get $2.71828203081$. Thus, in this we show that for $f(x) = (1+1/x)^x$, ...
2
votes
4answers
65 views
Prove that $2005|\underbrace{55 \ldots5}_{800\text{ digits}}$
Prove that $2005|\underbrace{55 \ldots 5}_{800\text{ digits}}$
I know that $2005=5\cdot 401$ since $55 \ldots 5$ is divisibility with $5$ i only need to prove that $55 \ldots 5$ is divisibility with ...
0
votes
0answers
34 views
Find conditions on $a, b, c$, and $d$ with $a\ne -1, 0, 1$ such that $d\mid(a^n+bn+c)$ for $n \ge 1$.
This is a generalization of
Using induction, show that $4^n +15n - 1$ is divisible by $9$ for all $n \geq 1$
I want to find conditions on
$a, b, c$, and $d$
with
$a\ne -1, 0, 1$
such that
$d\mid(a^n+...
-2
votes
1answer
19 views
Divison by Zero [duplicate]
I have seen multiple answers on the web, but I can't get my mind around why division by zero outputs an error and not zero. Can anyone explain this in laymen's terms?
0
votes
1answer
30 views
find a number $aabb$ such that is full square [duplicate]
I know that I can write $aabb=1000a+100a+10b+b$, $a,b\in \{0,1,2,3,4,5,6,7,8,9\}, a\neq 0$, so $aabb=1100a+11b=m^2$, where $m\in \mathbb N$, I notice that $m^2=11(100a+b)$ so I need to find some ...
0
votes
0answers
35 views
Prove $\frac{ab}{m} = \gcd(a,b)$ when $m=\operatorname{lcm}(a,b)$, for all natural numbers $a$ and $b$.
Prove $\frac{ab}{m} = \gcd(a,b)$ when $m= \operatorname{lcm}(a,b)$ for all natural numbers $a$ and $b$. I should be able to prove this using only basic rules of $\gcd$ and lcm.
I instead let $m$ be a ...
3
votes
2answers
51 views
$a\mid b^2, b\mid c^2, c\mid a^2\Longrightarrow abc\mid (a+b+c)^k$
Is it true that if $a,b,c$ are positive integers such that $a\mid b^2, b\mid c^2, c\mid a^2$, then $abc$ always divides $(a+b+c)^6$?
If not (I couldn’t find a counterexample), then $abc\mid (a+b+c)^7$...
0
votes
2answers
41 views
Prove that it does not exist two number such that $m^2+n^2=6 \underbrace {0 \cdots 0}$
Prove that it does not exist a two number $m,n\in \mathbb N$ such that $m^2+n^2=6 \underbrace {0 \cdots 0}$, in solution he choose to divide by 9, but i do not know why that number, I know that ...
3
votes
3answers
47 views
contradiction proof on divides
Suppose a,b ∈ Z. If 4 | $(a^2 + b^2)$ then a and b are not both odd.
So, assuming that 4 | $(a^2 + b^2)$ and $a$ and $b$ are odd
this gives $4k=(2l+1)^2+(2u+1)^2$ for some $k,l,u\in z$
eventually ...
1
vote
2answers
57 views
1
vote
5answers
48 views
For which $k$ can $(x-1)^{k} - (x+1)^{k}$ be divided by $x$?
Consider
$$
f_{n}(x) = (x-1)^{n} - (x+1)^{n}\,.
$$
For which $n$ can it be divided by $x$?
Explicitly I found that for $k = 1, 3$ $f_{n}(x)$ can not be divided by $x$, while for $n = 2$ It can. ...
0
votes
3answers
39 views
question on 'divides'
Let $a,b,c>0$ be natural numbers. Consider the following statments:
i) if $a\nmid b$ and $b |c$ then $a\nmid c$
ii) if $a |b$ and $b |c$ then $ab |bc$
iii) if $a |c$ and $b |c$ then $ab |c$
iv) ...
1
vote
1answer
21 views
Find the smallest number such that when you divide with $4,6,8,10,12$ the remainder is $2,4,6,8,10$
Find the smallest number such that when you divide with $4,6,8,10,12$ the remainder is $2,4,6,8,10$.
This is the solution:
Let $n \in \mathbb N$ such that $n = 4q_1 + 2$, for some $q_1$, $n = 6q_2 + ...
1
vote
1answer
40 views
Prove that number $1^{2005}+2^{2005}+\cdots+n^{2005}$ is not divisible by number $n+2$
Prove that number $1^{2005}+2^{2005}+\cdots+n^{2005}$ is not divisible by number $n+2$ for every $n\in \mathbb N$
I have solution $2(1^{2005}+2^{2005}+ \cdots +n^{2005})=2+(2^{2005}+n^{2005})+(3^{...
0
votes
0answers
16 views
Currency Conversion - Getting an equivalent % of currency outside of z/y pair
I am working with 3 currencies. I am trying to get a value (price of Y per Z) that is less 39X.
Let me elaborate with an example.
3% of 1300X = (39 X). I want to take 39X away from the Z/Y pair.
...
2
votes
1answer
33 views
Factors of Square Numbers
Let $n$ and $k$ be positive integers. Prove that if $n+k$ is a factor of $n^2$ then $k > \sqrt{n}$.
I do not really know how to approach this. I tried letting $(n+k)(n-m) = n^2$ for some positive ...
1
vote
1answer
50 views
N and M are positive integers having same digits but in different order, N + M = 10^10, then prove that N is divisible by 10.
"N and M are positive integers having same digits but in different order, $$N + M = 10^{10}$$ then prove that N is divisible by 10."
I have tried solving the question but to no avail. Please help.
0
votes
1answer
29 views
simple question on division
Does any natural number q divide 0 because there exists a natural number m such that qm=0 (m=0)?
Is it true that 0 does not divide any natural number >0, because there does not exist a number q such ...
0
votes
2answers
43 views
$\{ \frac{n}{2^k} = x \}$ , A simple Question that's bothering me.
I'm quite fascinated by the above Simple question. i.e.,
If I just make $k$ as big as, say $k \ge 10^8 $ , then it's quite heavy to compute the value of $2^k$.
My query is, if that becomes ...
4
votes
0answers
42 views
Non-Chen primes dividing $3^k+3$ and $2^k-3$
A non-Chen prime is a prime $p$ such that $p+2$ is neither a prime nor a semi-prime. $3^6+3=732$ is divisibile by the non-Chen prime $61$. On the other hand, $2^6-3=61$.
Are there infinitely many $...
2
votes
5answers
49 views
Find a remainder when dividing some number $n\in \mathbb N$ with 30
A number n when you divide with 6 give a remainder 4, when you divide with 15 the remainder is 7. How much is remainder when you divide number $n$ with $30$?
that mean $n=6k_1+4$, $n=15k_2+7$, and $n=...
1
vote
1answer
58 views
When do Co-Primes have a common factor?
If a and b are co-primes and $n$ is a prime then prove that $\frac{a^n + b^n}{a+b}$ and $(a+b)$ have no common factors unless $(a+b)$ is a multiple of $n.$
I am unable to proceed, please help.
0
votes
1answer
36 views
Finding the HCF
Find $(a^{2^m}+1, a^{2^n}+1)$ when a is odd and a,m,n are positive integers and m is not equal to n. I know that the hcf is a multiple of two but I can't prove that it is 2 which is the answer. Plz ...
0
votes
1answer
14 views
If (a, b) = d, then (a/d, b/d) = 1 [duplicate]
Proof.
Let c = (a/d, b/d).
Then c | a/d, and so cd | a.
Also c | b/d, and so cd | b.
My question is, did this happen because of this simple algebra?
ie. c | a/d
So cx = a/d for some integer ...
0
votes
3answers
42 views
Prove if d | a, then d | ca for any integer c. Correction [duplicate]
I am frustrated because this is literally exercise 3 from my textbook and I still can not get it. I already failed my first midterm. I am wondering why I am bad with discrete mathematics, but love ...
1
vote
0answers
38 views
Find a content of $(1 + w)x^4 + ( -1 + 2w )x^3 + (1-2w )x^2 + 3x + (2 + 3w ) \in \mathbb{Z}[w][x]$
Find a content of $(1 + w)x^4 + ( -1 + 2w )x^3 + (1-2w )x^2 + 3x + (2 + 3w ) \in \mathbb{Z}[w][x]$
My attempt:
I see that $w+1$ is a unit, $( -1 + 2w )$ and $(1-2w )$ are associates, $3=(1+2w)(1+...
2
votes
4answers
57 views
What is the remainder when $4^{10}+6^{10}$ is divided by $25$?
Without using calculator, how to decide? Must go with last two digits of $4^{10}+6^{10}$, can tell the last digit is $2$. How to tell the tenth digit of the sum?
Thanks!
0
votes
1answer
39 views
If a polynomial p(x) is divisible by (x-a)^n where nϵℕ and n≥2, then p(x) is divisible by (x-a)^(n-1)
I have no idea how to begin, I do know that if $p(x)$ is divisible by $(x-a)^n$ then we should have $p(x)=(x-a)^n*q(x)+r(x)$ where $r(x)=0$. And this seems like something I would want to try induction ...
0
votes
0answers
57 views
Proof verification: If $gcd(n,9)=3$ then $gcd(n^2,9)=9$, $p∣n \implies p∣n^2$, $p∣n^2\implies p∣n$.
1. gcd$(n,9)=3$ then gcd$(n^2,9)=9$
2. Let $p$ be a prime and $n \in \mathbb{N}$, if $p∣n$ then $p∣n^2$.
3. Let $p$ be a prime and $n \in \mathbb{N}$, if $p∣n^2$ then $p∣n$.
I'm not sure about ...
2
votes
1answer
37 views
$\gcd(a(X),\,a'(X))$ w.r.t. squarefree decomposition
We are considering polynomials over a field $\mathbb{F}$. For $a \in \mathbb{F}[X]$, we have a squarefree decomposition
$$
a = \prod_{i=1}^k a_i^i
$$
where $\gcd(a_i,\,a_j) = 1$ for $i \neq j$ and the ...
0
votes
2answers
37 views
Prove if $n\mid ab$, then $n\mid [\gcd(a,n) \times \gcd(b,n)]$
Prove if $n\mid ab$, then $n\mid [\gcd(a,n)\times \gcd(b,n)]$
So I started by letting $d=\gcd(a,n)$ and $e=\gcd(b,n)$.
Then we have $x,y,w,z$ so that $dx=a$, $ey=b$,$dw=ez=n$
and we also have $s$ so ...
1
vote
2answers
15 views
Is the equation $x = \phi(n), x=2k, n,k \in \mathbb{Z}$, where $\phi(n)$ is the Euler totient function, solvable for all evens?
I was just getting my hands dirty solving some equations of the form $x=\phi(n)$ where $\phi(n)$ is Euler totient function. I know that $\phi(n)$ is even for $n\geq 3$. However, I am wondering that:
...
0
votes
3answers
44 views
Do consecutive integers never divide each other? If not, why? [closed]
I was solving some number theory problems and it struck my mind. I am a beginner, so don't go hard on me.
0
votes
2answers
46 views
Prove that there are infinitely many integers $n$ such that $3\nmid\phi(n)$
My thoughts are to choose any number of the form $2^k$, $5^k$ or any number combined of both of these two like $10,50,100$ and so on. The reasoning follows from the closed form of $\phi(n)$. Sorry for ...
0
votes
0answers
39 views
Find largest $a, b \in \mathbb{N}$ so that $a \times b \geq n$
I have the following problem: I have $n$ images that I want to display on-screen. $n$ might be any number from $\mathbb{N}$. If I have one Image, I want this layout (* is an image, _ is empty space):
...
-1
votes
1answer
57 views
How to do 21/2 on paper
I looked at online tutorials and im stuck at this case.
21/2
First, 2 goes into 2 once, so put 1 in the quotient, 2*1 = 2 so 2-2 = 0. Now we bring the 1 in 21 down. 2 doesnt go into 0, so what do we ...
4
votes
6answers
111 views
Prove that $10|n+3n^3+7n^7+9n^9$
Prove that $10|n+3n^3+7n^7+9n^9$ for every $n\in \mathbb N$
Only what i see that 10=5*2 and both number is free numbers, and if I show that $5|n+3n^3+7n^7+9n^9$ and $2|n+3n^3+7n37+9n^9$ that I prove, ...
1
vote
1answer
53 views
$(n-1)! \equiv 0 \pmod n$, Wilson's Theorem version for non prime moduli [duplicate]
The question is to prove the following:
If $n>4$ is composite, then $(n-1)! \equiv 0 \pmod n$
My attempt to prove so is the following:
Since $n$ is not prime, the prime factors of $n$ lies ...
2
votes
2answers
36 views
how do i prove this (divisibility of integers)?
Let a, b, and c be integers. If a divides b OR a divides c, then a divides b*c. How do I prove the contrapositive?
4
votes
1answer
27 views
Is the repunit $R_{3^k}$ divisible by $3^k$?
By the repunit $R_n$ is meant the base ten positive integer consisting of $n$ digits all 1. My question is whether when $n=3^k$ we have the repunit divisible by $3^k$. I checked up to $R_{243}$, a ...
