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

learn more… | top users | synonyms

18
votes
2answers
508 views

Do there exist two primes $p<q$ such that $p^n-1\mid q^n-1$ for infinitely many $n$?

We can prove that there is no integer $n>1$ such that $2^n-1\mid 3^n-1$. This leads to the following question: Is it true that for every pair of primes $p<q$ there are only finitely many ...
0
votes
1answer
43 views

Prove that $GCD(a,b)=1$ if for all natural numbers $c, a|bc $ then $a|c$.

I'm trying to prove a theorem out of my text: Theorem: Let $a$ and $b$ be natural numbers. Then $GCD(a,b)=1$ if and only if for all natural numbers $c$, if $a|bc$ then $a|c$. I did come across this ...
0
votes
3answers
47 views

Let N be a four digit number, and N' be N with its digits reversed. Prove that N-N' is divisble by 9. Prove that N+N' is divisble by 11.

Let $N$ be a four digit number, and $N'$ be $N$ with its digits reversed. Prove that $N-N'$ is divisible by $9$. Prove that $N+N'$ is divisible by $11$. I let $N=abcd$ and $N'=dcba$ but I dont see ...
1
vote
2answers
207 views

Probability of getting a five digit number divisible by 5 but with no two consecutive digits identical

A five digit number is written down at random. What is the probability of getting a number that is both divisible by 5 and doesn't have any 2 consecutive digits identical? I tried to analyse the ...
0
votes
0answers
43 views

If $n \mid a^2 $, what is the largest $m$ for which $m \mid a$?

Given $n$, what is the largest $m$ such that $m \mid a$ for all $a$ with $n \mid a^2$? This is a generalization of if $40|a^2$ prove that $20|a$ when $a$ is an integer where $n=40$ and $m=20$. Here ...
0
votes
0answers
34 views

Is my limited understanding of division and gcd on track?

Hello I am trying to make sense of some beginner theorems and propositions in number theory. I am wanting to also know if what I am saying is valid or just completely wrong. I am wanting to show that ...
1
vote
1answer
21 views

Palindromes and LCM

A palindrome is a number that is the same when read forwards and backwards, such as $43234$. What is the smallest five-digit palindrome that is divisible by $11$? I'm probably terrible at math but ...
0
votes
1answer
34 views

Divisibility proof with GCD condition

Suppose $a|m$, $b|m$ and $\gcd(a,b) = 1$. Prove, without appealing to the fundamental theorem of arithmetic, that $ab|m$. I know that $\gcd(a,b)=1$ means they are relatively prime. I also know ...
2
votes
1answer
67 views

Prove $\gcd\left(\frac{a^m - 1}{a -1},a -1\right) = \gcd(m,a-1)$ [duplicate]

While studying the basics of arithmetic, I've found one problem that I'm not able to solve: Let a and m be two integers, $a \geq 2$ and $ m \geq 1$, with greatest common divisor $1$ ($\gcd(a,m) = ...
6
votes
6answers
2k views

Prove that $(a-b) \mid (a^n-b^n)$

I'm trying to prove by induction that for all $a,b \in \mathbb{Z}$ and $n \in \mathbb{N}$, that $(a-b) \mid (a^n-b^n)$. The base case was trivial, so I started by assuming that $(a-b) \mid (a^n-b^n)$. ...
2
votes
4answers
327 views

Proof that $3^c + 7^c - 2$ by induction

I'm trying to prove the for every $c \in \mathbb{N}$, $3^c + 7^c - 2$ is a multiple of $8$. $\mathbb{N} = \{1,2,3,\ldots\}$ Base case: $c = 1$ $(3^1 + 7^1 - 2) = 8$ Base case is true. Now assume ...
2
votes
3answers
99 views

For what powers $k$ is the polynomial $n^k-1$ divisible by $(n-1)^2$? [closed]

How do you prove this? $$\left(n-1\right)^2\mid\left(n^k-1\right)\Longleftrightarrow\left(n-1\right)\mid k$$
1
vote
4answers
79 views

If $3|(a^2 + b^2)$, show that $3|a$ and $3|b$. [duplicate]

I have no idea how to do this problem; please consider helping me: If $3|(a^2 + b^2)$, show that $3|a$ and $3|b$.
0
votes
3answers
43 views

How to prove if $m,n\in \mathbb{Z}$,then $30\mid mn(m^4 -n^4)$

I first thought I'd just have to do cases, i.e. if $m,n$ are even, $m=2l, n=2k$, where $k, l\in \Bbb Z$. But even in this case, alone, I wind up with $4kl(16l - 16k) = 64k(l^2) - 64l(k^2)\dots$ and ...
0
votes
5answers
63 views

How to prove that $7^{15} + 7^{16} + 7^{17} - 1$ is divisible by $10$?

This was a question on my math exam. We weren't able to use calculators so proving by manually calculating the exact value would take too long. In the end I ignored this question to save time but I'm ...
1
vote
2answers
89 views

Is 7^2015 + 4^2015 divisible by 17? Explain your reasoning and show your work.

Is $7^{2015} + 4^{2015}$ divisible by 17? Explain your reasoning and show your work. I'm confused on how exactly I would do this. Would I need to use Fermats Theorem?
26
votes
9answers
6k views

Why $a^n - b^n$ is divisible by $a-b$?

I did some mathematical induction problems on divisibility $9^n$ $-$ $2^n$ is divisible by 7. $4^n$ $-$ $1$ is divisible by 3. $9^n$ $-$ $4^n$ is divisible by 5. Can these be generalized as $a^n$ ...
1
vote
0answers
35 views

Looking applications for these statements involving multiplicative functions and Euler-Fermat theorem

It is well knwon that for positive integers such that $gcd(a,n)=1$, Euler-Fermat Theorem states than $a^{\phi(n)}\equiv 1 \mod n$, where $\phi(n)$ is the Euler totient function counting positive ...
2
votes
1answer
89 views

Expected number of digits of the smallest prime factor of $1270000^{16384}+1$

The number $N\ :=\ 1270000^{16384}+1$ with $100,005$ digits is given. Given, that $N$ is composite and does not have a prime factor below $2\times 10^{13}$, what is the expected number of digits ...
1
vote
2answers
189 views

What are the “units” and “non-trivial divisors of zero” in a ring?

I'm confused on what units and non-trivial divisors of zero are when it comes to rings. For example, say I have this finite ring: R=GF(2)[x] mod x^3 + 1 = 0. Now I know the elements are 0, 1, x, x + ...
3
votes
4answers
80 views

Prove that $5\mid 8^n - 3^n$ for $n \ge 1$ [duplicate]

I have that $$5\mid 8^n - 3^n$$ The first thing I tried is vía Induction: It is true for $n = 1$, then I have to probe that it's true for $n = n+1$ $$5 \mid 8(8^n -3^n)$$ $$5 \mid 8^{n+1} ...
0
votes
5answers
111 views

Prove: If $n^2$ is odd, then $n$ is odd. [duplicate]

$n$ is a natural number. I want to prove that, if the square of $n$ is odd, then $n$ itself is odd. Any hints welcome and preferred. Thank you!
-1
votes
2answers
77 views

Prove that if a|b, c|d, then ac|bd [duplicate]

I'm trying to prove it, but I can't find how. If a divides b, and c divides d, then ...
0
votes
2answers
89 views

Prime number between 7902 and 7918 [closed]

Which number between the interval 7902 & 7918 can be divided without remainder only to itself and to the number 1?
0
votes
2answers
55 views

Find two numbers given their product, GCD, and remainder of division of one by the other

$a$ and $b$ are two positive integers. If $ab=1260$, $gcd(a,b)=3$, and when $a$ is divided by $b$ the remainder is 18, what are $a$ and $b$? How do you solve this? It looks like an application ...
4
votes
1answer
97 views

When is $(12x+5)/(12y+2)$ not in lowest terms?

I am struggling to solve this problem and would appreciate any help: When is $\frac{12x+5}{12y+2}$ NOT in lowest terms? ($x$,$y$ are nonnegative integers) I have found that it is not in lowest ...
8
votes
6answers
7k views

Prove $\gcd(a+b, a-b) = 1$ or $\gcd(a+b, a-b) = 2$ if $\gcd(a,b) = 1$

I want to show that for $\gcd(a,b) = 1$ $a,b \in Z$ $\gcd(a+b, a-b) > = 1$ or $\gcd(a+b, a-b) = 2$ holds. I think the first step should look something like this: $d = \gcd(a+b, a-b) ...
-1
votes
2answers
50 views

Show that if $a, b$, and $c$ are integers with $(a,b)=(a,c)=1$, then $(a,bc)=1$ [duplicate]

Show that if $a, b$, and $c$ are integers with $(a,b)=(a,c)=1$, then $(a,bc)=1$ I don't know exactly that I should use the division algorithm or $(a,b)=d$, $(a/d,b/d)=1$. This is my first time ...
6
votes
1answer
67 views

$\frac{2n\choose n}{n+2}\not\in\mathbb N$ and $n\neq3k+1$ and $n\neq4k+2$

Are there any natural numbers $n\not\equiv1\bmod3$, and $n\not\equiv2\bmod4$, so that $~\dfrac{\displaystyle{2n\choose n}}{n+2}\not\in\mathbb N$ ? Since $C_n=\dfrac{\displaystyle{2n\choose ...
1
vote
1answer
36 views

Divisibility test using perhaps binomial thorem

I have to determine if $17^{21} + 19^{21}$ is divisible by any of the following numbers (a) 36 (b) 19 (c) 17 (d) 21. I am trying to find using binomial expansion but getting stuck up with one or two ...
5
votes
1answer
82 views

Maximum amount of divisors of the number $n^m+m^n$

We are given some positive integer $m$. What maximum amount of distinct prime divisors a number $n^m+m^n$ can have, where $n\in\mathbb{Z}_+$? Edit: As noted in comments, there is no reason to think ...
2
votes
3answers
215 views

Converting Decimal to Hexadecimal

MathExchange, I am trying to learn more about computers, and one thing I have opted to teach myself is decimal to binary, and decimal to hex conversion. From the web, I have found tutorials on ...
3
votes
0answers
18 views

Knapsack - Saving Waste

I am trying to figure out the most efficent way to save waste. I've looked into the knapsack problem as I believe it is what can help me solve this dilemma. Any help, guidence, or direction is ...
2
votes
2answers
487 views

The difference of two consecutive perfect squares is always odd

I am working on another homework assignment about proofs. The question is: Prove or find counterexample: the difference of two consecutive perfect squares is odd? There is no counterexample correct? ...
1
vote
3answers
111 views
0
votes
2answers
60 views

How do I show $1$ is not a trivial odd perfect number?

This question related to my this question in MO ,some comments stated that the integer $1$ is trivial answer for this question ,but here i'm very confused when we say that the sum divisors of $1$ is ...
2
votes
1answer
51 views

Number Theory Prime Reciprocals never an integer

I'm in number theory and I currently have these problems assigned as homework. I've looked through the sections containing these problems and I've solved/proved most of the other problems, but I can't ...
2
votes
2answers
104 views

If $a\mid b$ and $b\mid a$, then $a = b$ or $a = -b$. Is the converse true?

I was able to prove the original statement, but I'm stuck on the converse. If $a = b$ or $a = -b$, then $a\mid b$ and $b\mid a$. This holds true for $a = b = 1$, but I'm not sure how to proceed. I ...
1
vote
1answer
96 views

Consider the relation R given by divisibility on positive integers that is xRy <-> x|y

Consider the relation R given by divisibility on positive integers that is xRy <-> x|y Is this relation reflexive? symmetric? anti-symmetric? transitive?? I understand it is reflexive and ...
3
votes
1answer
52 views

Number Theory Positive Divisor Problems

I'm in number theory and I've been assigned these problems for homework. I've searched throughout the relevant section of the book but I can't seem to find anything that relates to solving these ...
2
votes
3answers
774 views

16 digit numbers divisible by 17

I wanted to know about the $16$ digit numbers those are divisible by $17$ and when this $16$ digit number is broken in groups of $4$ those groups of four are also divisible by $17$ and a check to ...
2
votes
2answers
48 views

Showing that a number is not divisible by another.

I am currently in a number theory class, but we don't have a textbook and even though I have been attending all the lectures we have not solved a problem similar to this in class. We have never proved ...
0
votes
1answer
22 views

How can I improve my basic proof about divisibility

Hello I am wondering if my approach is on the right track or not. I want to show that if $m \in \mathbb{Z}$ and $m \neq 0$ is a solution to the equation $x^2+ax+b=0$ where $a, b$ also are integers ...
2
votes
2answers
101 views

Number Theory: Prove there are infinitely many primes $p$ satisfying $n\mid (p-1)$

I've been assigned the following problem for my homework: For any $n\in N$ show there are infinitely many primes $p$ satisfying $n\mid (p-1)$. I think I've proved it, but I'm uncertain since we were ...
0
votes
0answers
12 views

Is division by $\sum x_i-\bar{x}$ actually null?

I'm trying to find out what are $\hat{β_1}, \hat{β_2}$ $ \left \{ \begin{array}{c @{=} c} \frac{∂S( \hat{β_1}, \hat{β_2})}{∂S \hat{β_1}} =-2\sum(yi − \hat{β_1} − \hat{β_2}xi) = 0, \\ ...
3
votes
4answers
463 views

If $a | b$, prove that $\gcd(a,b)$=$|a|$.

If $a | b$, prove that $\gcd(a,b)$=$|a|$. I tried to work backwards. If $\gcd(a,b)=|a|$, then I need to find integers $x$ and $y$ such that $|a|=xa+yb$. So if I set $x=1$ and $y=0$ (if $|a|=a$) ...
2
votes
0answers
52 views

How can I construct a number $n$, such that $gcd(n+k,100!)\ne 1$ for all $k=0,…,256$

Here : https://oeis.org/search?q=2%2C4%2C6%2C10%2C14%2C22%2C26%2C34%2C40%2C46&sort=&language=german&go=Suche it is indirectly claimed that there exists a number $n$, such that $n+k$ has ...
-1
votes
1answer
25 views

Why does this condition check the expectation?

Let's suppose n as an Integer. Let's suppose i as an Integer. To check whether the given i ...
2
votes
3answers
115 views

How to prove that $4^n-3n-1$ is divisible by 9?

How can I prove that $4^n-3n-1$ is divisible by $9$? I tried dividing the expression by $9$ and seeing if the terms cancelled in any predictable way but I still cannot prove it. Maybe there is a ...
0
votes
0answers
19 views

Why can we not let variable $p$ equal the number such that when multiplied by zero equals one.

Suppose we have a variable p such that when multiplied by zero equals one. In such case suppose when we do $1/0 = p$. This would satisfy the case $(1/0) \cdot 0 = 1$ again. Why do we not have a ...