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

learn more… | top users | synonyms

0
votes
2answers
52 views

Efficient way to check if large number is divisible by 3

If Mp=2p-1 is prime ⇒ ⇒ 2p-2⋮6 or 2p⋮6 ⇒ ⇒ 2p-1-1⋮3 or 2p-1⋮3 ⇒ ⇒ 2n-1⋮3 or 2n⋮3, n=p-1 In order to pick huge values for p to test if Mp is a prime number, I believe this is a good preliminary ...
0
votes
1answer
28 views

subtract two 4-digit numbers and obtain the sum of the digits always 18

Let (abcd) and (dcba) be 4-digit numbers and (abcd)-(dcba)= (xyzt) show that the sum of the number (xyzt) is always 18. I think we will use divisibility rules but i could not succeed...
3
votes
2answers
92 views

Showing that if $(a,b)=1$ and if $a\mid c$ and $b\mid c$ then $ab \mid c$, in GCD domains

Is there a proof for the problem below? $R$ is a commutative, integral domain with unity in which for each pair $a,b\in R$, g.c.d. $(a,b)$ exists. I want to show that if $(a,b)=1$ and if $a\mid c$ ...
2
votes
2answers
44 views

Prove $3 \mid x-2 \implies 3 \mid (x^2 - x+1)$ using division algorithm

I can't figure out how to prove the following implication using the division algorithm: $$3 \mid x-2 \implies 3 \mid (x^2 - x+1)$$ It seems simple enough. Does anyone know how?
1
vote
0answers
24 views

Unwind quaternion multiplication

I am trying to understand quaterions division. Imagine I have the following equation, where every member is a quaternion: $$Q = (qq_1)(qq_2)...(qq_n)$$ I suppose that, if I maintain the order of ...
-2
votes
2answers
186 views

Divisibility of subsets of the set $1, 2, 3, …, n$ [closed]

Let $n$ be an even positive integer. Can one divide the numbers $1, ..., n$ into three nonempty groups, so that the sum of numbers in the first group is divisible by $n + 1$, in the second one by $n + ...
2
votes
2answers
59 views

if $5\nmid a$ or $5\nmid b$, then $5\nmid a^2-2b^2$.

I have a homework as follow: if $5\nmid a$ or $5\nmid b$, then $5\nmid a^2-2b^2$. Please help to prove it. EDIT: MY ATTEMPT Suppose that $5\mid a^2-2b^2$, then $a^2-2b^2=5n$,where $n\in Z$, then ...
4
votes
2answers
68 views

Simple question about dividing by zero, $y=\frac{x}{x}$ when $x=0$

Is there a rule that says you have to simplify equations before evaluating them? Would $y=\frac{x}{x}$ at $x=0$ be $1$ or undefined, since without reducing it, you'd divide by $0$. I know the equation ...
2
votes
3answers
64 views

Prove divisibility with gcd: If $ar+bs=d=\gcd(a,b)$, then $r$ and $s$ are relatively prime

I have this math problem. The question is: Suppose that $a$ and $b$ are positive integers, with $d = \gcd(a, b)$. Suppose that there exists integers $r$ and $s$ so that $ar + bs= d$. We ...
8
votes
2answers
196 views

If a divisor of $pq-1$ divides the LCM of $p-1$ and $q-1$, then it also divides the GCD of these two numbers

Suppose that $p,q$ are distinct odd primes. Suppose an integer $k$ divides $pq-1$ and also $k|\operatorname{lcm}(p-1,q-1)$. Show that $k|\operatorname{gcd}(p-1,q-1)$. I've spent ages looking at ...
1
vote
0answers
25 views

Prove that $AB\mid CD$

I have this math question that I'm kind of confused on. This is the question: Let $A, B, C$ and $D$ be integers with $A \mid C$ and $B \mid D$ show that $$ AB \mid CD. $$ I'm not 100% sure ...
7
votes
3answers
265 views

Proof that $n+k+3$ divides $n(n+1)(n+2)(n+3) - k(k+1)(k+2)(k+3)$.

I'm looking for proof that $$ (n+k+3) \mid n(n+1)(n+2)(n+3) - k(k+1)(k+2)(k+3)\\ n,k \in \mathbb N^*, n>k $$ I tried using induction, but i'm not sure how it would work with 2 parameters.
1
vote
1answer
133 views

LCM of $n$ consecutive natural numbers

Is there an efficient way to calculate the least common multiple of $n$ consecutive natural numbers? For example, suppose $a = 3$ and $b = 5$, and you need to find the LCM of $(3,4,5)$. Then the LCM ...
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
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 ...
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) = ...
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 ...
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 ...
1
vote
2answers
88 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?
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 ...
1
vote
1answer
57 views

How to prove: if $a$ is an even integer, $\gcd(a^3 - 1, a + 1) = 1$

I have very little idea of how to tackle this question. I know if $a$ is even, $a = 2L$, for some $L$ in the integer set.
3
votes
4answers
77 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} ...
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 ...
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
votes
2answers
75 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
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
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 ...
2
votes
2answers
192 views

Order of group element divides order of finite group

Proving this can be done as follows: consider a finite group G and elements $g_i \in G$ for some integer $i$. Now consider $\langle g_i \rangle = \{g_i^n: n\geq 0\}$, a generator. It can be proved ...
1
vote
1answer
56 views

If $r$ is a nonzero solution $ x^2 + ax + b$, prove that $r | b$

I know that if $r$ is a solution, then there exist two factors of $b$ that when multiplied equal $b$ and that $r$ is one of them. So clearly $r$ divides $b$, but I don't know if there is any other way ...
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 ...
1
vote
3answers
110 views

divisibility question: if two integers can both divide each other, do they have to be equal? [duplicate]

if x ,y ∈ Z. and x|y,y|x,then x does NOT equal to y. Can anyone give me a counter example please?
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 ...
4
votes
2answers
55 views

Prove that $2^n+(-1)^{n+1}$ is divisible by 3.

Prove that $2^n+(-1)^{n+1}$ is divisible by 3 for $n\in\mathbb{N}$. My attempt: For $n=1$: $2^1+(-1)^2 = 2 + 1 = 3, 3 |3$ We assume that $3|(2^n+(-1)^{n+1})$ Then for $n+1$: $2^{n+1} + ...
2
votes
2answers
122 views

Prove these two elements are not associated in $\mathbb Q[x,y,z]/(x-xyz)$ [duplicate]

So the full problem was: Consider $R=\mathbb Q[x,y,z]/(x-xyz)$. Prove that $x$ and $xy$ divide each other in $R$ but that they are not associates. In other words, there is no unit $u\in R$ so ...
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 ...
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
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, \\ ...
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 ...
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$) ...
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 + ...
-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 ...