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

learn more… | top users | synonyms (1)

3
votes
1answer
244 views

On an exponential diophantine equation

I am trying to find all integer solutions of $5^x + 12 ^y$ = $13^z$. The obvious (and pursued) solution is $(2, 2, 2)$, and no others. I've tried to use an appropriate modular arithmetic, but to no ...
2
votes
1answer
177 views

The biquadratic character of $2$ mod $p$ for a prime of the form $p = 4n + 1$

It seems that Gauss states the following theorem in his first paper of biquadratic residues(Werke vol. II pp. 67-92). I cannot read Latin, but I have a Japanese translation of the paper. However, it ...
4
votes
0answers
81 views

The number of solutions of $ax^4 - by^4 \equiv 1$ (mod $p$) for a prime of the form $p = 4n + 1$

Weil writes in his paper "The number of solutions of equations in finite fields" that Gauss finds the number of solutions of $ax^4 - by^4 \equiv 1$ (mod $p$) for a prime of the form $p = 4n + 1$ in ...
1
vote
1answer
69 views

Property of congruence given a square-free modulus

Problem Suppose $n$ is square-free and $\alpha,\beta,\gamma \in \mathbb{Z}_n$. I want to show that $\alpha^2 \beta = \alpha^2 \gamma \implies \alpha \beta = \alpha \gamma$. Current Work If $n$ is ...
3
votes
2answers
90 views

How to solve $\binom{n-k}{m-k} \approx A$ for positive $k$?

How to find a positive integer $k$ satisfying $\binom{n-k}{m-k} \approx A$ given $n,m,A$ ? For example how to find $k$ satisfying $\binom{32-k}{7-k} \approx 260000$ ? Using trial and error I found ...
0
votes
3answers
139 views

Prove that ${3^{2}}^{n} + 1$ when divided by $2^{2}$, always gives a remainder of 2, where $n$ is a natural number.

$P(n)=3^{{2}^{n}} + 1$ $P(1)=3^{{2}^{1}} + 1$ $P(1)=10=4*2+2$ $P(2)=3^{{2}^{2}} + 1$ $P(2)=82=4*20+2$ ... ... ... $P(k)=3^{{2}^{k}} + 1$
4
votes
1answer
126 views

Sum of all invertible integers modulo a prime

If $p$ is an odd prime, I want to show that $$\sum_{\beta \in \mathbb{Z}_p^\ast} \beta^{-1} = \sum_{\beta \in \mathbb{Z}_p^\ast} \beta = 0$$ Now I know $\mathbb{Z}_p^\ast = \{1,\dots,p-1\}$, so ...
2
votes
1answer
36 views

Finite set of congruences

Is it true that for every $c$ there is a finite set of congruences $a_i(mod\,\,n_i) , c = n_1<n_2<n_3<...........<n_k \,\,\, (1)\\ $ So that every integer satisfies at least one of ...
10
votes
8answers
2k views

Prove that $\gcd(M, N)\times \mbox{lcm}(M, N) = M \times N$.

I'm not sure how to go about this proof. I just need help getting started. Is there a way to prove it algebraically?
0
votes
2answers
37 views

let $A$ be any inductive set, then $\{C \in P(A)|C \text{ is inductive set} \}$ is a set? … and $\mathbb{N}$…?

let $A$ be any inductive set, then $\{C \in P(A)|C \text{ is inductive set} \}$ is a set? if $\{C \in P(A)|C \text{ is inductive set} \}$ is a set I can defined $\mathbb{N}:=\bigcap\{C \in P(A)|C ...
21
votes
1answer
587 views

Why did Gauss think the reciprocity law so important in number theory?

Gauss's Disquitiones Arithmeticae centers around the quadratic reciprocity law. It seems that he developed the genus theory of integral binary quadratic forms to find a natural proof of the quadratic ...
1
vote
2answers
82 views

Any way to simplify $\gcd(a+b,a-c)$?

If I have the expression $\gcd(a+b,a-c)$ is there a way to further reduce this? Are there any other properties?
7
votes
1answer
100 views

On the Pell-like $Ax^2-By^2 = 1$

This is connected to the post, Mere coincidence? (prime factors). I was looking at NeuroFuzzy's dataset and noticed the line, {{{1, {4, 2}}, {1, 4, 2, 4, 2}, 23762}} It seems this could be ...
1
vote
3answers
142 views

definition of $\mathbb{N}:=\bigcap Ind$

--- let $A$ a set, $A^+=A \cup \{A\}$ --- let $B$ a set, B is inductive if $\emptyset \in B \wedge \forall A \in B(A^+ \in B )$ --- let $Ind:=\{C|C \text{ is inductive }\}$ is correct this ...
-2
votes
2answers
90 views

Find all the five digit primes with this property

Find all the five digit prime numbers such that the product of their digits equals some number squared multiplied by another number such as 7^2 * 5 for example.
1
vote
2answers
2k views

What is the remainder of $6^{17}$ divided by $17^6$?

What is the general method to solve such questions ?
4
votes
4answers
160 views

Are there any integer solutions to $2^x+1=3^y$ for $y>2$?

for what values of $ x $ and $ y $ the equality holds $2^x+1=3^y$ It is quiet obvious the equality holds for $x=1,y=1$ and $x=3,y=2$. But further I cannot find why $x$ and $y$ cannot take ...
1
vote
1answer
184 views

Linear equation with prime coefficient.

Suppose we have a linear equation with two variables say $x$ and $y$ and three integer coefficient $a , b$ and $c$ (constant), where $a$ and $b$ are prime all are greater than zero. $ax+by=c$ how ...
3
votes
1answer
125 views

The structure of $(\mathbb Z/525\mathbb Z)^\times$

I am working on the following problem. Find the number of the elements of order 4 in $(\mathbb Z/525\mathbb Z)^\times$. I tried to solve it in the following way: since $525=3\cdot5^2\cdot7$, we ...
0
votes
2answers
135 views

Proof involving Chinese Remainder Theorem.

Problem: Suppose $n_1,n_2$ are positive integers, $d = \gcd(n_1,n_2)$, and $a_1, a_2$ are integers. I want to show that there exists an integer $a$ such that $a \equiv a_1 \;(\!\!\!\!\mod n_1)$ and ...
4
votes
1answer
170 views

More general form of Chinese Remainder Theorem

Suppose $\{n_i\}_{i=1}^k$ are pairwise prime natural numbers, $a_1,\dots,a_k,b_1,\dots,b_k$ are integers, and $d_i = \gcd(a_i,n_i)$ for $i=1,\dots,k$. I want to show that there exists an integer $z$ ...
0
votes
1answer
49 views

Find positive fractions so that $k_1+k_2+…+k_n+k_{n+1} \leq 1/2^n$?

I'm working on a proof in topology and the only thing left to do is some combinatorics (number theory?), which I've never had any exposure to. I would appreciate any help I can get. I'm attempting ...
1
vote
2answers
129 views

Prove: $f(x)^{p^k}\equiv f\left(x^{p^k}\right)\bmod p$

$p$ is a prime number, $k$ is an positive integer, and $f\in\Bbb Z[x]$. Prove: $f(x)^{p^k}\equiv f\left(x^{p^k}\right)\bmod p$
4
votes
1answer
408 views

Let $p$ be a prime and $q$ a prime divisor of $2^{p} -1$. Use Fermat's Little Theorem to prove that $q\equiv 1 (\mod \space p)$

Question continued: Hint: Consider $ord_{q}(2)$. Similarly, prove that if $r$ is a prime factor of $2^{2^{k}}+ 1 $ then $r\equiv1 (\mod \space 2^{k+1})$ I think I have the first part, however I ...
8
votes
3answers
238 views

Prove that there are exactly 16 solutions to this problem.

Show that are are only 16 integer solutions to the following equation: $$11x + 8y + 17 = xy$$ What I tried: I took a modulo 2, and I got that $y$ must be even and $x$ must be odd. But beyond that, I ...
1
vote
1answer
132 views

Integral form for the euler-mascheroni gamma constant using floor function

Im trying to prove that: $$\gamma = \lim_{n \to\infty} ( \sum_{1}^n \frac{1}{n} - \log(n)) = 1 - \int_{1}^{\infty} \frac{t- \lfloor t \rfloor}{t^2} dt = 1 - \int_{1}^{\infty} \frac{ \{ t \}}{t^2}dt$$ ...
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
165 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?