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)

4
votes
3answers
320 views

The greatest common divisor of $a$ and $b$ is a linear combination of $a$ and $b$. In general, in what kind of ring does this hold?

In $\mathbb{Z}$, the greatest common divisor of $a$ and $b$ is a linear combination of $a$ and $b$. This generalizes to Euclidean domains since Euclid's algorithm works. Moreover this statement ...
1
vote
4answers
528 views

Does such a natural number exist, that it would be divisible by every other natural number

I've got to prove (or disprove) the following statement: $\exists x \in \mathbb{N} \; \forall y \in \mathbb{N}: y \mid x$, which translates into "It exists such $x$ from the set of natural numbers, ...
1
vote
3answers
35 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
94 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 ...
32
votes
8answers
3k views

What is $\gcd(0,0)$?

What is the greatest common divisor of $0$ and $0$? On the one hand, Wolfram Alpha says that it is $0$; on the other hand, it also claims that $100$ divides $0$, so $100$ should be a greater common ...
2
votes
4answers
218 views

How to show $a^{2^n}+1 \mid a^{2^m}-1$?

I've been struggling with this all day today. I imagine it's not very hard, but my algebra skills are terrible. So, how can I show that if $m>n$ and $a$ is a positive integer, then $$a^{2^n}+1 \mid ...
1
vote
2answers
4k views

If $\gcd(a,b)=1$ and $a$ and $b$ divide $c$, then so does $ab$

Using divisibility theorems, prove that if $\gcd(a,b)=1$ and $a|c$ and $b|c$, then $ab|c$. This is pretty clear by UPF, but I'm having some trouble proving it using divisibility theorems. I was ...
0
votes
2answers
179 views

If $a \mid c, b \mid c, \gcd (a,b)=1$ then $ab \mid c.$ [duplicate]

If $a \mid c, b \mid c, \gcd (a,b)=1$ then $ab \mid c.$ I understand that given problem is true. however im struggling with writing to prove. I let A=2 , B= 3 , C= 6 2 l 6= 3 3 I 6=2 3*2 l 6=1 ...
3
votes
6answers
157 views

Prove that if $n^2$ is divided by 3, then also $n$ can also be divided by 3.

$n\in \Bbb N$ Prove that if $n^2$ is divided by 3, then also n can also be divided by 3. I started solving this by induction, but I'm not sure that I'm going in the right direction, any ...
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
49 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
1answer
51 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
80 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 ...
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)$ ...
2
votes
5answers
93 views

Prove that if $3\mid n^2 $ then $3\mid n $. [duplicate]

$n \in \mathbb{N}$ Prove that if $3\mid n^2 $ then $3\mid n $ I want to prove this in a accepted formal way, I thought about the fact that every integer can be written as multiplication of prime ...
0
votes
1answer
99 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 ...
0
votes
1answer
54 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
32 views

To prove for every integer $k >1 $ , $2+2^k \choose r$ is even for all $2 < r \le n=1+2^{k-1}$ , without Lucas' theorem

Can we prove by induction that for every integer $k >1 $ , $2+2^k \choose r$ is even for all $2 < r \le n=1+2^{k-1}$ ? Or by some divisibility properties of Binomial co-efficients ? I wanted to ...
0
votes
2answers
45 views

GCD proof using fundamental theorem of arithmetic

prove: $\gcd(m,n)=1$ if and only if $\gcd(m^i,n^r)=1$ I believe you need to do something with fundamental theorem of arithmetic to prove one of the sides. Not quite sure though. Help is appreciated. ...
3
votes
2answers
36 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?
3
votes
2answers
66 views

How to find a Fibonacci number that is divisible by $x$?

I'm looking for an algorithm that is better than just checking every number in the Fib Sequence for divisibility. Example: Find the first Fib number that is divisible by $x=223321$, with no ...
4
votes
0answers
32 views

Given n , what is the sum of all gcd integers upto n with n? [duplicate]

Given an integer n, I want to find S = gcd(1,n) + gcd(2,n) + gcd(3,n) + ....gcd(n,n). Now , there are I have firgured that the number should be something like S = φ(n) + x. Now I can't draw a ...
3
votes
1answer
1k views

Sum of GCD(k,n)

I want to find this $$ \sum_{k=1}^n \gcd(k,n)$$ but I don't know how to solve. Does anybody can help me to finding this problem. Thanks.
3
votes
1answer
60 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 terms for ...
1
vote
2answers
44 views

Linear congruence fill in the missing step?

Currently working on this problem and I'm having trouble seeing how it goes from one line to the next. $45x \equiv 63\mod 11$ goes to $x \equiv 8\mod 11$ Any help would be awesome thanks. ...
-1
votes
1answer
394 views

Count permutations with LCM

Given $N,M$ and $D$ we need to count how many permutations of $N$ integers are there with each $i$'th element $1 \le A[i] \le M$ such that least common multiple (LCM) of all its elements is divisible ...
1
vote
3answers
59 views

If p is an odd prime, prove that $a^{2p-1} \equiv a \pmod{ 2p}$

Let $m = 2p$ If p is an odd prime, prove that $a^{2p - 1} \equiv a \pmod {2p} \iff a^{m - 1} \equiv a \pmod m$. I have no idea on how to start. I was trying to find a form such that $a^{m - 2} ...
3
votes
1answer
125 views

Proving $a\mid b^2,\,b^2\mid a^3,\,a^3\mid b^4,\ldots\implies a=b$ - why is my approach incorrect

Theory Number Problems After I saw that post i wanted to solve the first one which is $a\mid b^2,b^2\mid a^3,a^3\mid b^4,b^4\mid a^5\cdots$ Prove that $a=b$ Now i started by proving that $a$ and $b$ ...
0
votes
1answer
26 views

Does $ p|(2^{2kq}-2^{kq}+1)$ where $p=1+k\cdot q$ ? I'm stuck…

Does $ p|(2^{2kq}-2^{kq}+1)$ ,$p=1+k\cdot q$,where $p,q$ are prime ? From Fermat's little theorem; $(2^{2kq}-2^{kq}+1)$ mod $q\equiv (2^{2k}-2^{k}+1)$ This is where I'm stuck, please help. Thank ...
4
votes
1answer
75 views

Prove that $(z^3-z)(z+2)$ is divisible by $12$ for all integers $z$

I am a student and this question is part of my homework. May you tell me if my proof is correct? Thanks for your help! Prove that $(z^3-z)(z+2)$ is divisible by $12$ for all integers $z$. ...
5
votes
3answers
6k views

The product of n consecutive integers is divisible by n! (without using the properties of binomial coefficients)

How can we prove, without using the properties of binomial coefficients, the product of n consecutive integers is divisible by n factorial?
11
votes
1answer
169 views

Are there infinitely many pairs of primes where one divides one more than the square of the other?

I have the following question on number theory that is eating my head. Are there infinitely many primes $p,q$ such that $p | (q^2 + 1)$ and $q | (p^2 + 1)$? I can see $13,5$ and $2,5$ has the ...
0
votes
1answer
28 views

Number theory hcf confusion

I need to show 11|(100a+b) if and only if 11|(a+b). The solution: 11|(100a+b) iff 11|(100a+b-99a) so obviously 11|(a+b) and we have the solution as easily as that. However I cannot see why this is ...
0
votes
0answers
21 views

Form of Divisors of Proth numbers

Proth number is a number of the form : $z⋅2^k+1$ where z is an odd positive integer and k is a positive integer such that : $2^k>z$ Is there a form for divisors of Proth Numbers? (Like Mersenne ...
1
vote
1answer
32 views

$n,a,b \mathbb \in \mathbb Z^+$ , such that $n\mid a^n-b^n$ ; to show $n\mid \frac {a^n-b^n}{a-b}$ [duplicate]

Let $n,a,b \in \mathbb Z^+$ be such that $n\mid a^n-b^n$ , then how to prove that $n\mid {\dfrac {a^n-b^n}{a-b}}$ ? My try : $d=\gcd(n,a-b),$ so $d \mid{\dfrac {a^n-b^n}{a-b}}.$ Also $\,n ...
5
votes
3answers
104 views

Solve: $ab+bc+ca\mid (a+b+c)^2$

I couldn't make any progress on this problem, can anyone help? I found it's the same as: Find all integers $a,b,c$ such that $ab+bc+ca$ divides $a^2+b^2+c^2$. I found a solution $a=-b=1$, and $c$ ...
3
votes
4answers
48 views

Prove that if $na=mb$ and $(a,b)=1$, then $m=a$ and $n=b$.

I'm sorry but I'm having a massive brain fart. I'm trying to show that if $na=mb$ and $(a,b)=1$, with $a,b,n,m \in \mathbb{N}$ of course, then $m=a$ and $n=b$. Moving to $\mathbb{Q}_+$, we note that ...
1
vote
2answers
51 views

If $n^m\mid m^n$ and $k^n\mid n^k$, prove $k^m\mid m^k$, $m,n,k\in \mathbb{Z}^+$

If $n^m\mid m^n$ and $k^n\mid n^k$, then $k^m\mid m^k$, $m,n,k\in \mathbb{Z}^+$ Aside from the definition of divisibility, can someone suggest theorems/facts that might be useful in proving this ...
4
votes
1answer
48 views

To prove ${2p - 1 \choose p } \equiv 1 \pmod{p^2}$ without using Wolstenholme's theorem

How to prove that ${2p - 1 \choose p} \equiv 1 \pmod{p^2}$ ? I don't want to use Wolstenholme's theorem; but one might use $p|{p \choose k} , 1 \le k \le p - 1$ , and $(p - 1)! \sum_{k = 1}^{p - 1} ...
3
votes
3answers
63 views

Proving $ab(a+b)+ac(a+c)+bc(b+c)$ is even

Prove that $\forall a,b,c\in \mathbb N: ab(a+b)+ac(a+c)+bc(b+c)$ is even I tried to simplify the expression to something that would always yield an even number: $ (a+b+c)(ab+ac+bc)-3abc$ but ...
0
votes
1answer
47 views

Formula of MIPS (million instructions per second)

Could you please help me to understand the mathematics behind MIPS rating formula? The performance of a CPU (processor) can be measured in MIPS. The formula for MIPS is: $$MIPS = \frac{Instruction \ ...
1
vote
1answer
15 views

If $n \in \mathbb Z^+$ , $a,b$ are integers such that $d=g.c.d.(a-b,n)$ , then $d^2|a^n-b^n$ ?

If $n \in \mathbb Z^+$ , $a,b$ are integers such that $d=g.c.d.(a-b,n)$ , then is it true that $d^2|a^n-b^n$ ?
0
votes
1answer
15 views

Find $a+b$ for $a, b$ such that $(x+1)^{n}(x^{2}+ax+b) \equiv 2^{n}(x-1) \mod (x-1)^{2}$

Since $2^{n} = \sum_{0}^{n}\binom{n}{k},$ we have from the given congruence the congruence $$\sum_{0}^{n}\binom{n}{k}(x^{k+2} + ax^{k+1} + bx^{k} - x +1) \equiv 0 \mod (x-1)^{2}.$$ The given answer ...
1
vote
2answers
46 views

For every natural number $n$, $ 3^{3n} - 1$ is divisible by $26$.

Use induction to prove that for every natural number $n$, $ 3^{3n} - 1$ is divisible by $26$. I can see that for $n=1$, $ 3^{3} -1=26\cdot 1$. As for inductive step, assuming that the statement ...
-1
votes
2answers
88 views

Proof that if x is prime, then x+7 is composite. [closed]

Proof that if x is prime, then x+7 is composite. I do not know how to prove it. Can anyone help me to solve it? Thx
-2
votes
2answers
49 views

If $a,b,c\neq0$, prove that $ac\mid bc \iff a\mid b$ [closed]

How can I prove this question? If $a,b,c\neq0$, prove that $ac\mid bc \iff a\mid b$ Please help me
0
votes
4answers
77 views
2
votes
1answer
52 views

implication of a number dividing a product of relatively prime numbers

I read this recently on the web and can't manage to understand it. Not homework -- I haven't done math homework for years. If $d|ab$ and $(a,b)=1$, prove that $d=d_1 d_2$, that $d_1|a$, that $d_2|b$, ...
2
votes
5answers
129 views

The divisibility of $a^p-1$ by $a-1$ and by $(a-1)^2$

I was working my way through some number theoretic proofs and being a newbie am stuck on this problem : Let a $\geq$ 2 and p be any positive integers , then prove that : $(a-1) \mid(a^p - ...
6
votes
5answers
319 views

Proving an expression is composite

I am trying to prove that $ n^4 + 4^n $ is composite if $n$ is an integer greater than 1. This is trivial for even $n$ since the expression will be even if $n$ is even. This problem is given in a ...