Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms

0
votes
0answers
30 views

Modified Lucas-Lehmer Test

Conjecture (Modified LL) Let $M_p=2^p-1$ such that $p$ is odd prime and $p\equiv 5 \pmod{6}$ . Let $S_i=S_{i-1}^8-8\cdot S_{i-1}^6+20\cdot S_{i-1}^4-16 \cdot S_{i-1}^2+2$ with $S_0=4$ , then $M_p$ ...
3
votes
5answers
91 views

How to select the right modulus to prove that there do not exist integers $a$ and $b$ such that $a^2+b^2=1234567$?

I understand the solution but I don't know how the author decided to start with modulo 4 instead of something else? What is it about the expression $a^2+b2=1234567$ that would trigger us to select ...
1
vote
1answer
37 views

Prove that $\sum_0^n({nCr})^2=2nCn$

Prove that $\sum_{r=0}^n({nCr})^2=2nCn$ I don't know how to prove such probems. Any proof by combinatorics?
3
votes
4answers
56 views

Prove that $\gcd (n^3-1,n+1)=1$ for all even $n$.

Prove that if $n$ is even, then $$\gcd(n^3-1,n+1)=1.$$ I really don't have a clue with this one. Any help would be appreciated.
0
votes
1answer
33 views

Euler's Theorem when $m$ is square-free

Suppose that $m$ is square-free, and that $k$ and $\bar{k}$ are positive integers such that $k\bar{k} \equiv 1\pmod{\phi(m)}$. Show that $a^{k\bar{k}} \equiv a \pmod m$ for all integers $a$. In the ...
3
votes
1answer
129 views

Weird question? Smallest positive whole number?

I have a math question I can't figure out... Suppose you move the last digit of a positive whole number to the front of the number. (i.e 142 becomes 214 and 1234 becomes 4123) Find the smallest ...
0
votes
3answers
33 views

Canonical decompositions and product of primes

Let $S$ be the set of natural numbers $n$ that have exactly $9$ positive divisors. Describe all possible canonical decompositions (as products of primes) of elements of $S$.
1
vote
1answer
42 views

How do you prove this theorem?

The theorem I have to prove is ...
0
votes
0answers
13 views

Is there a proof for Algorithm of test of Selfness of a number?

Is there a known proof for the algorithm given by D.R.Kaprekar for test of a SELF NUMBER? I want to know the proof because it is something that can't be proved by general methods we use.
3
votes
5answers
143 views

Find a possible n such that $(2^n +3^n)/{113}$ is integer

Find an $n$ such that $(2^n +3^n)/{113}$ is an integer. So essentially, $2^n + 3^n$ has to become a multiple of $113$ for some $n$. I have tried to solve it algebraically, but it is impossible ...
0
votes
1answer
29 views

Find a solution using a Diophantine equation

The diophantine equation is 3a + 12b = 132 From the textbook, I set out to find the gcd(3,12) which is 3. then I proceed to set up the equation 3s+12t = 0 for any integer s and t 0 = 12(1) + 3(-4) ...
3
votes
2answers
61 views

How to descend within the “Tree of primitive Pythagorean triples”?

It is well-known that the set of all primitive Pythagorean triples has the structure of an infinite ternary rooted tree. What is the exact algorithm (i.e., formula, or possibly set of three formulas) ...
1
vote
2answers
98 views

How to show that $a,\ b\in {\mathbb Q},\ a^2+b^2=1\Rightarrow a=\frac{s^2-t^2}{s^2+t^2},\ b= \frac{2st}{s^2+t^2} $

I want show the following $$a,\ b\in {\mathbb Q},\ a^2+b^2=1\Rightarrow a=\frac{s^2-t^2}{s^2+t^2},\ b= \frac{2st}{s^2+t^2},\ s,\ t\in{\mathbb Q} $$ How can we prove this ? [Add] Someone implies that ...
1
vote
3answers
63 views

Divisibility by primes

Suppose that $n$ is a natural number, $n \ge 2$, and $n$ satisfies: For each prime divisor $p$ of $n$, $p^2$ does not divide n. If $p$ is prime, $p$ divides $n$ if and only if $(p − 1)$ divides $n$. ...
2
votes
1answer
66 views

Find all positive integers $(x,y,z)$ such that $\frac{1}{x}+\frac{1}{y}+\frac{1}{z}$ is integer

As stated in title, I would like to find solution to this problem: Find all positive integers $(x,y,z)$ such that $\frac{1}{x}+\frac{1}{y}+\frac{1}{z}$ is also integer. I need idea how to solve ...
2
votes
2answers
52 views

If $q$ is a prime $\leq p$, then $q$ divides $p\# − q$

If $q$ is a prime $\leq p$, then $q$ divides $p\# − q$ What does this mean? I know that it is related to something which I have been studying, but what does $p\# − q$ mean? I am only beginning to ...
4
votes
3answers
115 views

Prove the gcd $(4a + b, a + 2b) $ is equal to $1$ or $7$.

So in the question it says to let $a$ and $b$ be nonzero integers such that $\gcd(a,b) = 1$. So based on that I know that $a$ and $b$ are relatively prime and that question is basically asking if the ...
0
votes
1answer
30 views

Diophantine equation $(x^2-1)^2-4y^2=0$

We have the diophantine equation $(x^2-1)^2-4y^2=0$, where $x$ and $y$ are positive integers. Is the only solution $x=1$, $y=0$ or can there be infinitely many solutions?
1
vote
3answers
23 views

If $a,b$ are positive integers such that $\gcd(a,b)=1$, then show that $\gcd(a+b, a-b)=1$ or $2$. and $\gcd(a^2+b^2, a^2-b^2)=1$ or $2 $

If $a,b$ are positive integers such that $\gcd(a,b)=1$, then show that $\gcd(a+b, a-b)=1$ or $2$ and $\gcd(a^2+b^2, a^2-b^2)=1$ or $2 $. Progress We have $\gcd(a,b)=1\implies \exists u,v\in ...
1
vote
2answers
35 views

Homework gcd. Show that $gcd(a_1,a_2,a_3,…a_k) = gcd(gcd(a_1,a_2),a_3,…a_k)$

Help me with this please show that $gcd(a_1,a_2,a_3,...a_k) = gcd(gcd(a_1,a_2),a_3,...a_k)$ How can I start?
0
votes
3answers
25 views

Given that $\gcd(a,2)=2$ and $\gcd(b,4)=2$, prove that $\gcd(a+b, 4)=4$

Given that $\gcd(a,2)=2$ and $\gcd(b,4)=2$, prove that $\gcd(a+b, 4)=4$ $\gcd(a,2)=2\implies 2\mid a\implies a=2q_1$ for some $q_1\in \mathbb Z$ $\gcd(b,4)=2\implies 2\mid b\implies b=2q_2$ for ...
1
vote
1answer
42 views

$13$ divides $10^{2p}-10^p+1$ for any prime $p > 3$

In a curse of number theory I need show that for any prime $p > 3$ prove that $13$ divides $10^{2p}-10^p+1$. but I failed You can help me? Thanks!
1
vote
4answers
77 views

Can anyone explain how to show that $n^{5} -n ≡0$ mod $30$ for every $ n \in \mathbb{N} $

I first tried to answer this using proof by induction, however my problem got more complicated when I got to the induction step. Is there another way of solving this problem?
2
votes
1answer
36 views

proof a mathmatical statement

If $\,\mathrm{gcd}(a,b)=1,\;d=ac,\;$ and $\,b\mid d,\,$ then $\,b\mid c.$ For example, $45=9\times 5$ is divisible by $3$ and $\mathrm{gcd}(3,5)=1$ and $3$ divides $9$. But it is easily ...
2
votes
0answers
118 views

The congruence $\{(a^m, a^{m+r})\}^\#$ on $a^+$.

I've spent a bit too long on this exercise. It's time to ask for help. This is Exercise 1.20 of Howie's Fundamentals of Semigroup Theory. Let $\rho_{m, r}$ (for $m, r\ge 1$) be the congruence ...
1
vote
1answer
39 views

One Half of a Primorial

Is there a name for a half primorial? How should a half primorial be notated? The first three primorials are 2,6, and 30. The first three half primorials are 1,3, and 15. I have found that the half ...
1
vote
4answers
52 views

Show that $4$ does not divide $12x+3$ for any $x$ in the integers.

I'm not exactly sure where to start on this one. Any help would be greatly appreciated. Show that $4$ does not divide $12x+3$ for any $x$ in the integers. Here's what I have so far: There exist c ...
52
votes
11answers
9k views

Am I just not smart enough? [closed]

When I was doing math, let us say for example, introductory number theory, it seems to take me a lot of time to fully understand a theorem. By understanding, I mean, both intuitively and also ...
0
votes
1answer
72 views

I just want to know is this is correct without a proof

Let $a$, $b$, $c$ be integers. If $a\mid c$ and $b\mid c$, then $ab\mid c$. I say yes but I want to know if I'm correct
1
vote
1answer
40 views

How do I apply Fermat's little theorem to these kinds of problems?

I have just learned Fermat's little theorem. That is, If $p$ is a prime and $\gcd(a,p)=1$, then $a^{p-1} \equiv 1 \mod p$ Well, there's nothing more explanation on this theorem in my book. And ...
3
votes
1answer
50 views

If the permuted set of $(1,2, \dots n ) $ is such that sum of any two adjacent numbers is a square. Find the generalized form of $n$.

$ \text{Let}$$ P(n) \text{be permutation of}$$ (1,2 \dots n)$$ \text{such that if}$$ P(n)={a_1,a_2, \dots a_n} $$ \text{then} $$(a_i+a_{i+1})=k^2$$ \text{where}$$ k\in \mathbb{N}$ and $i \in {1,2,3, ...
2
votes
1answer
54 views

What is the maximum difference between two successive real numbers in the given floating point representation?

The following is a scheme for floating point number representation using 16 bits. Sign :- Bit 15 Exponent:-Bit 14-9 Mantissa :- Bit 8-0 Let $s, e,$ and $m$ be the numbers represented in binary in ...
2
votes
4answers
35 views

Generators of a product of finite abelian groups

Let $n_1,...,n_r$ be positive integers. Consider the group $$G={\bf Z}/n_1 {\bf Z} \times \cdots\times {\bf Z}/n_r {\bf Z}$$ When does a given element $(k_1,\cdots,k_r)$ generate $G$? Obviously ...
0
votes
1answer
23 views

Combinations of sets raised to the power of a prime modulus

This is a problem out of the text Introduction to the Theory of Numbers by Niven, Zuckerman, and Montogmery and I am having quite a bit of trouble with it. I tried to prove it directly, but that ...
0
votes
2answers
143 views

Prove this induction problem [closed]

Show that every positive integer $N$ less than or equal to $n$ factorial, is the sum of at most $n$ distinct positive integers, each of which divides $n!$.
0
votes
0answers
13 views

Solving congruence $x^2 \equiv 1 \mod{2^{\alpha}}$

At the end of case 3, I'm not seeing how $2^{\alpha - 1} | (x + 1)$ or $2^{\alpha - 1} | (x - 1)$ implies that $x \equiv 2^{\alpha - 1} - 1 \pmod{2^{\alpha}}$ and $x \equiv 2^{\alpha - 1} + ...
0
votes
0answers
53 views

Proof for divisibility on a prime test: (p-1)!/(n!(p-n)!)

$p$ is a prime only if $\forall n \in\{ 2, 3, .. ,\lfloor \frac{p}{2}-1\rfloor, \lfloor \frac{p}{2}\rfloor \}$: $\dfrac{(p-1)!}{n!(p-n)!}\in \mathbb N$ The remainders and n's that don't divide when ...
1
vote
1answer
29 views

Prove the inequality $p_{n+1}<{2^{2^n}}$

Problem: Let $p_n$ be the nth prime. Prove that $$p_{n+1}<{2^{2^n}}$$ Hint: note that $p_1 \cdot p_2\cdot ...\cdot p_n +1 \geq p_{n+1}$ I'm stuck in this problem , I don't even know how to prove ...
1
vote
2answers
29 views

Showing $x^2 = 1\pmod{p^{\alpha}}$ has only two solutions?

In the $p | x - 1$ case, I'm a little confused about some of the latter steps; in particular, how does knowing that $$\exists y \ s.t. (x+1)y \equiv 1\pmod{p^{\alpha}}$$ tell us that $$(x^2 - ...
1
vote
2answers
27 views

Numbers $9a+4$ and $2a+1$ are relative primes for $a\in\mathbb{Z}$

Show that the positive integers of the form $9a+4$ and $2a+1$ with $a\in\mathbb{Z}$ are relative primes, i.e, show that $\gcd(9a+4, 2a+1)=1$
0
votes
0answers
43 views

How to prove the following logical statement

Prove that for every pair of integers $a$ and $d$ such that $d < 0$, there exists a pair of integers $q$ and $r$ such that $a=qd+r$ and $0≤r<−d$. (Note that this claim is not the same as the ...
0
votes
3answers
33 views

Proving the GCD

Let $a= 16673011647$. Let $b = 16213295811$. Using the fact that $a \times −77566962 + b \times 79766315 = 51$, prove that $51$ is the gcd of $a$ and $b$. The part that is confusing is, using the ...
1
vote
2answers
26 views

Interesting use of remainder theorem

I am asking this question in reference to this post Write an Efficient Method to Check if a Number is Multiple of 3 In the proof of the method the author writes that any 2 digit number(AB) can be ...
3
votes
0answers
49 views

Are there any positive integers $a, b, c, d$ such that both $(a, b, c)$ and $(b, c, d)$ are Pythagorean triples?

Pythagorean triple is a triple of integers $(a, b, c)$ such that $a^2+b^2=c^2$. Is there any Pythagorean triple such that, not only $a^2+b^2$, but also $b^2+c^2$ is a square number? If not, how to ...
0
votes
6answers
60 views

Prove that if $\gcd (m,n)=1$ and $m\mid x$ and $n\mid x$, then $mn\mid x$.

I've come across the statement that if $\gcd (m,n)=1$ and $m\mid x$ and $n\mid x$, then $mn\mid x$. (This is needed for a proof of the correctness of RSA that I have been given.) I can't see how to ...
2
votes
0answers
23 views

Significance of formulas similar to summation formula

We all know formula $n(n+1)/2$ for adding up the numbers from $1$ to $n$. But I would like to know if there is any significance and use of formulas of type $n(n^{p-1}+p-1)/p$, where $p$ is a prime. ...
1
vote
4answers
57 views

$z^2=x^2+y^2$ Prove that $4\mid xyz$ ($xyz$ is divided by $4$)

$z^2=x^2+y^2$ where $x,\ y,\ z$ - integers Prove that $4\mid xyz$ ($xyz$ is divided by $4$) All possible rest in divided by $4$ in this case is $1$. That's all I noticed.
1
vote
1answer
54 views

Find all positive integer that $2^{2^n}+5 $ is a prime number. [duplicate]

Find all nonnegative integer that $2^{2^n}+5 $ is a prime number. For $n=0$ we have $7$ - correct For $n=1$ we have 9 - false For $n=2$ we have 21 - false For $n=3$ we have 259 ... Maybe any ideas ...
1
vote
1answer
19 views

Greatest Common Divisor of $2$ Numbers in The Integers

How do I find the numbers s and t in The Integers ${\mathbb Z}$ such that: $$21s + 8t = {\rm gcd}(21,8) $$
1
vote
2answers
42 views

Does Goldbach's Conjecture Imply This?

Every natural number $\geq 4$ is centered between a pair of primes or is itself prime. Is this implied by Goldbach's conjecture?