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
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

Determine the remainder

Determine the remainder when $2^{2018}$ is divided by $55$
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 ...