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

learn more… | top users | synonyms (1)

0
votes
2answers
3k views

How to find modular multiplicative inverse

For example: $$63x \equiv 1 (mod 17)$$ I wanna find the multiplicative inverse here so that I can use this in the Chinese reminder theorem. Example: $$x \equiv 2 (mod 3)$$ $$x \equiv 4 (mod 5)$$ ...
3
votes
1answer
114 views

Prove $\forall a,b,k \in \Bbb Z^+$ such that $a \equiv -1 \bmod 3$ and $b \equiv 1 \bmod 3$, $2^{2k-1}a,2^{2k}b$ are non-trivial polygonal numbers

Below is my original question, which has since been modified to a more general form. Prove that $\forall p,q \in \Bbb P$ and $k \in \Bbb Z^+$ such that $q \equiv -1 \bmod 3$ and $p \equiv 1 \bmod 3, ...
3
votes
0answers
68 views

Isn't zero natural enough to be included in the set of natural numbers? [duplicate]

I always define $\mathbb{N}$ to include $0$ but some authors don't. Since the elements of $\mathbb{N}$ are used for counting, shouldn't $0\in\mathbb{N}$? $0$ is the number of cows in a classroom for ...
1
vote
2answers
54 views

How many fourth powers are below $n^2$?

Given $n^2$, how many fourth powers $(x^4)$ are between 0 and $n^2$? $n,x\in \mathbb{Z}$ Does this just reduce down to how many squares are below $n$?
1
vote
4answers
463 views

Divisibility and the Fibonacci sequence

While studying the Fibonacci sequence I encountered this problem in the handout, and I can not understand how to do it. Show that if the Fibonacci sequence has a term divisible by a natural number ...
0
votes
1answer
102 views

Two issues of Number Theory

Knowing in Fibonacci sequence$$u_n\mid u_m\Longleftrightarrow n\mid m$$ Question 1: In Fibonacci sequence, show that $$5\mid u_m\Longleftrightarrow 5\mid m$$ Show: $\Longrightarrow$ In ...
2
votes
3answers
209 views

Statement on the Fibonacci sequence

Question: Let $n,m,\in\mathbb{N^*}$ with $n>1$ and let $u_n$ denote the $n$-th term of the Fibonacci sequence, then $$u_{n+m}=u_{n-1}u_m+u_nu_{m+1}$$ I know these theorems: Two consecutive ...
1
vote
2answers
207 views

Twin, cousin, and sexy prime property

Why the digital root of twin primes is always $(2,4) (8,1) (5,7)$? Why the digital root of two primes with difference $4$ is always $(4,8) (1,5) (7,2)$?
2
votes
0answers
116 views

Express $10$ as a difference of consecutive primes in $15$ ways

How would you express $10$ as a difference of two consecutive primes in $15$ different ways? I started by constructing the classic Diophantine equation in two variables: $(1)x + (-1)y = 10$ But, ...
3
votes
3answers
577 views

Prove that if $n > 4$ is composite $n|(n-1)!$

Let $n = p_1^{q_1}p_2^{q_2}p_3^{q_3}\dots p_n^{q_n}$ where each $p_i$ is a prime and less than $n$ and each $q_i \geq 1$. We are required to prove that $n |(n-1)!$. For this to be true every $p_i$ ...
0
votes
1answer
103 views

Weird result by manipulating Wilson's Theorem

The Wilson's Theorem says that a number $n$ is prime iff $(n-1)! \equiv -1 \space (mod \space n)$, right? This would mean: $\begin{align*}1\cdot 2\cdot 3\dots (n-1) \equiv -1 \space (mod \space ...
1
vote
0answers
166 views

Can an odd perfect number be divisible by 101?

Preamble - This question is an offshoot from the following earlier questions here at MSE: Can an odd perfect number be divisible by 825? Can an odd perfect number be divisible by 165? Odd perfect ...
7
votes
1answer
452 views

Prove that $5$ is the only prime $p$ such that $3p + 1$ is a perfect square

Prove that $5$ is the only prime $p$ such that $3p + 1$ is a perfect square. I started off with assuming that $p$ is odd (since $2$ clearly does not satisfy). This would mean that $3p + 1$ is even. ...
1
vote
2answers
52 views

Let $a, m, n\in\mathbb{N^{*}}$ With $m>n$. Show ${(a^{2^m}-1,a^{2^n}+1)=a^{2^n}+1}$

Let $a, m, n\in\mathbb{N^{*}}$ With $m>n$. Show $${{(a^{2^m}-1,a^{2^n}+1)=a^{2^n}+1}}$$$$$$My thoughts: If we could show that $$(a^{2^n}+1)\mid (a^{2^m}-1)$$ the property that gcd says "If ...
1
vote
2answers
104 views

Problem of Ages (Problema das Idades)

English: Somebody help me with this challenge? It's very confusing: Today, both me and my younger brother are between $10$ and $20$ years old. Also, our ages are expressed by prime numbers and the ...
4
votes
1answer
162 views

Does this theorem have a name?

Let P(x) be a polynomial of degree n. Let H(i) represent the number of 1's in the binary expansion of the integer i. Although reasonably easy to prove, it may seem surprising that the following ...
-2
votes
1answer
1k views

Every integer greater than 1 is divisible by a prime [closed]

Every integer greater than $1$ is divisible by a prime. Prove it by mathematical induction (of weak form).
1
vote
0answers
88 views

Prime Numbers and Primitive Roots

Let $p_1$, $ p_2$, $p_3$ different prime numbers. Let $N = p_1p_2p_3$. Given $(p_1-1)|(N-1), (p_2-1)|(N-1)$ and $(p_3-1)|(N-1)$, prove that for every number $a \in \Bbb N$ such that $\gcd(a,N) = 1$ ...
2
votes
2answers
289 views

Generate all k-weight n-bit numbers in pseudo-random sequence.

I was generously introduced to the LFSR here not long ago. I am looking to take that a little further. I want to generate an Maximum length sequence of k-weight n-bit numbers in such a way that the ...
0
votes
1answer
55 views

I am looking for a general solution for $xy+x+y=n^2$ anyone able to help?

Is there a general formula for any $x$ and $y$ such that $xy+x+y=n^2$ for rational numbers (and some $n$?) Thanks =)
1
vote
1answer
58 views

If $p$ is irreducible and $p \not \mid a$, then $\text{gcd}(p,a)=\pm 1$.

I will be taking a Rings and Fields course in the Fall, so I figured I would read ahead in the textbook (A First Course in Abstract Algebra, by Anderson and Feil) to prepare. Recall the following ...
2
votes
2answers
102 views

Prove that if $d\cdot e| d(d+1)+e\cdot e$ then $d\cdot (d+1)+e\cdot e=3de$

Prove that if $d\cdot e| d(d+1)+e\cdot e$ then $d\cdot (d+1)+e\cdot e=3de$ where $d$ and $e$ are positive integers.
0
votes
3answers
68 views

If $x^2\equiv1\pmod5$, what can be said about $x \pmod5$?

(ENC 2000) If $x^2\equiv1\pmod5$, $x\in\mathbb{N},$ then: A) $x\equiv1\pmod5$ B) $x\equiv2\pmod5$ C) $x\equiv4\pmod5$ D) $x\equiv1\pmod5$ or $x\equiv4\pmod5$ E) ...
5
votes
1answer
102 views

The remainder of the division of $2^{100}$ by $11$ is $1$?

$$2^{10}\equiv 1\;\text{mod}\;11\Longrightarrow(2^{10})^{10}\equiv1^{10}\;\text{mod}\;11\Longrightarrow2^{100}\equiv1\;\text{mod}\;11\;\;?$$$$$$Soon, the rest will be $1$, correct?
4
votes
2answers
124 views

$7^{10}$ by $51$ what rest?

How to find the remains of Division $7^{10}$ by $51$ using arithmetic debris? $$$$ $$7\equiv51\;\text{mod}11$$
9
votes
1answer
612 views

How to justify the solution of this problem?

Assume $\mathbf{x} \in \mathbb R_+^N$ with support $P=\{p_1,p_2,\cdots,p_K\}$ ($P$ is unknown). We already know that $$f_1(\mathbf{x}) = f_2(\mathbf{x}) = \cdots = f_{N-1}(\mathbf{x})$$ where ...
1
vote
1answer
149 views

Solutions in complex number field, instead of $\mathbb{N}$, to Fermat's Last Theorem

As far as I know, we are searching solutions in set of positive integers for $x^n + y^n = z^n$ for $n > 2$. There are many proofs are stated that Fermat is true and there is no solutions for this ...
1
vote
7answers
379 views

How do I test if a number $x$, is a sum of consecutive natural numbers?

How do I test if a number $x$, is a sum of consecutive natural numbers? For example my test is passed for $55$ as it is $1 + 2 + 3 + \ldots + 10$ but fails for $54$? Edit: The numbers start with 1 ...
2
votes
1answer
180 views

No primitive roots modulo $N = pqr ( p , q , r$ all primes$)$

Let $p,q,r$ be distinct prime numbers. I tried to prove that there is no primitive root modulo $N = p\cdot q\cdot r$ without much success. I'd be grateful if anyone could point me to the solution. ...
0
votes
2answers
190 views
2
votes
2answers
219 views

Show that $2^a + 1 $ is divisible by 3 if a is odd.

I understand that this question has been asked before, but I was wondering if I could get clarification in understanding the accepted answer by @Hagen von Eitzen. (Sorry no plagiarism here is ...
1
vote
4answers
1k views

Find all congruence solutions using Hensel's Lemma

I have to find all the solutions to the congruence $x^2 = -6(\text{mod}\, 625)$ using Hensel's lemma and I find it quite difficult. If anyone could point me to the solution I'll be grateful, thanks in ...
4
votes
1answer
138 views

Prove that $\sqrt[3] {3n^2+3n+1} \notin \mathbb{N^+}$ given that $n \in \mathbb{N^+}$

I need to prove that, assuming $n \in \mathbb{N^+}$ $$\sqrt[3] {3n^2+3n+1} \notin \mathbb{N^+}$$ I'm really stuck with this problem, because so far I haven't managed a clever way to solve it. Also, ...
2
votes
1answer
75 views

Prove that both $4m^2+17n^2$ and $4n^2+17m^2$ cannot be perfect squares for positive integers $m$ and $n$.

Prove that both $4m^2+17n^2$ and $4n^2+17m^2$ cannot be perfect squares for positive integers $m$ and $n$. I tried square bounding but didn't get very far. Thanks for any help.
1
vote
3answers
105 views

algebraic geometry and elliptic curves

Does $ax^2+by^2=cz^2$ have positive integer solutions? I know that the solution exists when $(a,b,c)=(1,1,1)$ or $(1,1,n^2+1)$, but I failed to produce a general formula. Any help would be ...
0
votes
1answer
69 views

Diophantine equation and cyclicity of $\mathbb{F}_p^*$

I am trying to prove that the diophantine equation $$1998^2x^2+1997x+1995-1998x^{1998}=1998y^4+1993y^3-1991y^{1998}-2001y$$ has no solution in integers (given that $1997$ is a prime). To do so, ...
2
votes
3answers
69 views

Multiples and decimal expansion…

If $d \in \{1;\cdots;9\}$ and $x \in \mathbb{N^*}$, $N_d(x)$ denotes the number of digits equal to $d$ in the decimal expansion of $x$. If $n$ and $m$ are in $\mathbb{N^*}$, is there $a$ in ...
0
votes
1answer
113 views

Foundations of number theory / basic arithmetic assumptions

On the first page of Hardy, Wright'a An Introduction to Theory of Numbers, they write: ...
-1
votes
2answers
119 views

What is a relationship between sets and Factorials of Non-Natural number?

We know that factorial of natural number n describes how many bijections there are from some set with k cardinality into itself. But what if cardinality of the set is non natural number? or what if ...
1
vote
1answer
109 views

General set of integer solutions $(p,q)$ to $1 = pa + qb$ for integers $a,b$ such that $\gcd(a,b)=1$

Given $a,b,c$ are positive integers satisfying that $\gcd(a,b)=1$ and $c \geq (a-1)(b-1)$, I want to show there are non-negative integers $s,t$ such that $c = as + bt$. As $\gcd(a,b) = 1$ and $c$ is ...
1
vote
0answers
36 views

Reasoning about $\left\lfloor\frac{p_k\#}{p_{k+1}}\right\rfloor$

This is a follow up question to my previous question. Let $$v_i = \left\lfloor\frac{ip_k\#}{p_{k+1}}\right\rfloor + c_i$$ where: $c_i \in \left\{1,2\right\}$ so that $v_i$ is odd and $v_ip_{k+1} ...
1
vote
1answer
32 views

Trying to understand why a set of residues modulo a primorial $p_k\#$ has a range of values smaller than $2p_{k+1}$

I've been reviewing the following: $$v_i = \left\lfloor\frac{ip_k\#}{p_{k+1}}\right\rfloor + c_i$$ where: $c_i \in \left\{1,2\right\}$ so that $v_i$ is odd and $v_ip_{k+1} > ip_k\# > ...
2
votes
0answers
69 views

Improving Montgomery product

I am reading the paper "A Cryptographic Library for the Motorola DSP56000" (http://link.springer.com/content/pdf/10.1007%2F3-540-46877-3_21.pdf) which describes a trick to speed-up calculation of the ...
4
votes
1answer
109 views

Is this proof rigorous?

"There is no rational number whose square is $\displaystyle \frac{m}{n}$, where $\displaystyle \frac{m}{n}$ is a positive fraction in lowest terms, unless $m$ and $n$ are perfect squares. For suppose, ...
4
votes
2answers
81 views

Solving $x \equiv 9 \pmod{11}, x \equiv 6 \pmod{13}, x \equiv 6 \pmod{12}, x \equiv 9 \pmod{15}$

$$x \equiv 9 \pmod{11}$$ $$x \equiv 6 \pmod{13}$$ $$x \equiv 6 \pmod{12}$$ $$x \equiv 9 \pmod{15}$$ Does this system have a solution? I want to solve this using the Chinese remainder theorem, but ...
1
vote
3answers
71 views

$\gcd(a,b_1 \cdots b_k)=1$ if an only if $\gcd(a,b_i) = 1$ for $i = 1,\dots,k$

Suppose that $a,b_1,\dots,b_k$ are integers and I want to show that $\gcd(a,b_1 \cdots b_k)=1$ if and only if $\gcd(a,b_i) = 1$ for $i = 1,\dots,k$. In the direction of assuming $\gcd(a,b_1 \cdots ...
20
votes
1answer
409 views

Does there exist a general solution of this 'Counting numbers' game?

A few days ago, a friend of mine taught me a number-game. It may be famous, but I haven't known it. I'm going to show it to you. Imagine that you have a kind of page-a-day calendar, and that you play ...
3
votes
2answers
101 views

For what $n$ is it true that $(1+\sum_{k=0}^{\infty}x^{2^k})^n+(\sum_{k=0}^{\infty}x^{2^k})^n\equiv1\mod2$

Let $A:=\sum_{k=0}^{\infty}x^{2^k}$. For what $n$ is it true that $(A+1)^n+A^n\equiv1\mod2$ (here we are basically working in $\mathbb{F}_2$.) The answer is all powers of 2, and it's fairly simple ...
2
votes
1answer
103 views

Determine all positive integers $n$ for which $B_n=\{0\}$.

Let $A_1,A_2,...,A_n,...$ and $B_1,B_2,...,B_n,...$ be sequences of sets defined by $a_1=\emptyset$, $B_1=\{0\}$, $A_{n+1}=\{x+1|x\in B_n\},B_{n+1}=(A_n\cup B_n)\setminus(A_n\cap B_n)$. Determine all ...
4
votes
0answers
89 views

Pairwise sums are equal

The distinct positive integers $a_1,a_2,...,a_n,b_1,b_2,...,b_n$ with $n\ge2$ have the property that the $\binom{n}2$ sums $a_i+a_j$ are the same as the $\binom{n}2$ sums $b_i+b_j$ (in some order). ...