Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.
2
votes
0answers
43 views
Prime numbers problem - discrete math
Show that natural numbers of the form $n^2+1$ are not divisible by primes of the form $p=4k-1$.
I can't really find a place to start.
Thank you very much in advance,
Yaron.
2
votes
2answers
57 views
A slight variation on the Pythagorean theorem
Are there any solution to $$a^2+b^2=c^2+1 $$ where $a \not=0$ and $b\not=0$
This is a follow-on from a previous question For what $n$ and $m$ is this number a perfect square?, which ultimately boils ...
2
votes
2answers
46 views
On the Pell-like $px^2-qy^2 = 1$ for prime $p,q$
Given any prime of form $p_n = u^2+nv^2$ for non-zero integers $u,v$. Consider,
\begin{aligned}
&p_2x^2-2y^2 = 1\\
&p_3x^2-3y^2 = 1\\
&p_7x^2-7y^2 = 1\\
&p_{11}x^2-11y^2 = 1\\
...
3
votes
1answer
50 views
What's the asymptotic distribution of $p^n$ (powers of primes)?
We know by the prime number theorem that
$\lim_{n\to\infty}\frac{\pi(n)}{n\,/\ln n} = 1$
An even better approximation is
$\lim_{n\to\infty}\frac{\pi(n)}{\int_2^n\frac{1}{\ln t}\mathrm{d}t} = 1$.
Is ...
1
vote
1answer
25 views
HINT for summing digits of a large power
I recently started working through the Project Euler challenges, but I've got stuck on #16 (http://projecteuler.net/problem=16)
$2^{15} = 32768$ and the sum of its digits is $3 + 2 + 7 + 6 + 8 = ...
1
vote
2answers
42 views
Simple Number Theory Question
Lets say I have number in decimal form to the ten-thousands place $$p=0.abcd$$ and another number $$q=0.xyz$$ to the hundredth place. $$a.b,c,d,x,y,z$$ are all integers from 0 to 9, inclusive, except ...
2
votes
1answer
31 views
Solving modular equations that gives GCD = 1
I have problems with understanding modular equations that gives GCD = 1. For example:
$$3x \equiv 59 \mod 100$$
So I'm getting $GCD(3, 100) = 1$. Now:
$1 = -33*3 + 100$
That's where the first ...
7
votes
0answers
106 views
A contest question
$p$ is an odd prime,denote $$f(x)=\sum_{k=0}^{p-1}\binom{2k}{k}^2x^k.$$
Prove that for every $x\in Z$,$$(-1)^\frac{p-1}2f(x)\equiv f(\frac{1}{16}-x)\pmod{p^2}.$$
This is a contest question,I do not ...
2
votes
1answer
62 views
Most elegant/simple proof of the irrationality of $\pi$
What is the most elegant/shortest proof of this? The proofs I have seen are quite long, unlike the proof of the irrationality of $e$.
thanks
2
votes
2answers
91 views
For what $n$ and $m$ is this number a perfect square?
Find all positive integers $n$ and $m$ such that $$(2mn+1)^2-4mn(m+n)+n^2+m^2+(n-1)^2+(m-1)^2-3$$ is a perfect square.
Of course $n=m=1$ is a trivial solution and if you put $n=m+1$ (assume WLOG that ...
0
votes
2answers
52 views
Prove that there exists an integer $a$ such that $\frac{a^2-x}{p}\in \mathbb{Z}$
Let $x$ be an odd number, $y$ a positive integer, and $p$ an odd prime number such that $x^2+y^2=p$. Show that there exists an integer $a$ such that $\dfrac{a^2-x}{p}\in \mathbb{Z}.$
This problem is ...
1
vote
0answers
36 views
How many “$1$” is need at least for a decimal number,which is consisting of “$0$” and “$1$” and divisible by $p$?
How many "$1$" is need at least for a decimal number,which is consisting of "$0$" and "$1$" and divisible by $p$?
If $p=2^k\cdot d+1$, and $10^d\equiv 1 \pmod p$,then $10^n\equiv -1 \pmod p$ has no ...
1
vote
0answers
26 views
(probability + algebra ) in cryptography.
Suppose we know $n$ - which is a product of two unknown primes
- and also an integer m such that $a^m \equiv$ 1 mod n for all a prime to
n. We see that any such m must be even (as we see by taking a ...
5
votes
2answers
76 views
When is it solvable:$10^a+10^b\equiv -1 \pmod p$
If $p$ is a prime, $(a,p)=1$,denote $ord(a,p)=d,$ where $d$ is the smallest positive integer solution to the equation $a^d\equiv 1 \pmod p$.We can prove that $$10^n\equiv -1 \pmod p\tag1$$ is ...
2
votes
0answers
49 views
Putting a sum of rational numbers over a common denominator
This comes up whenever we try to put a sum of rational numbers over a common denominator.
Let $\mathrm{lcm}$ denote the function that returns the lowest common multiple of a sequence of natural ...
0
votes
0answers
39 views
Legendre's proofs of commutativity and associativity of multiplication
I want a clarification for the demonstration of commutativity and associativity in multiplication law given in the introduction of Legendre's book An assay of number theory.
I understand the first ...
4
votes
2answers
60 views
For every prime of the form $2^{4n}+1$, 7 is a primitive root.
What I want to show is the following statement.
For every prime of the form $2^{4n}+1$, 7 is a primitive root.
What I get is that
$$7^{2^{k}}\equiv1\pmod{p}$$
...
1
vote
2answers
76 views
A binary quadratic form: $nx^2-y^2=2$
For which $n\in\mathbb{N}$ are there $(x, y)\in\mathbb{N}^2$ such that $nx^2-y^2=2$ ?
0
votes
2answers
48 views
Formulas for calculating pythagorean triples
I'm looking for formulas or methods to find pythagorean triples. I only know one formula for calculating a pythagorean triple and that is euclid's which is:
$$\begin{align}
&a = m^2-n^2 \\
&b ...
11
votes
2answers
91 views
Find the minimum of $q$.
Given $\displaystyle p,q\in\mathbb N, \frac p q=0.123456789...$(i.e. the first 9 digits after decimal point are $123456789$). Find the minimum of $q$.
I guessed the answer to be $111111111$ as ...
8
votes
1answer
146 views
Sum of square root of primes
I was playing around with prime numbers and a question came into my mind:
Let $S(n)$ denote the sum of square roots of primes from $2$ to the $n$th prime number.
Are there infinitely many numbers $n$ ...
1
vote
2answers
57 views
If $2n+1$ and $4n+3$ are prime, then $2n-1$ and $4n+1$ are not when $n>2$
How do you prove that, for $n>2$, if $2n+1$ and $4n+3$ are prime numbers, then $2n-1$ and $4n+1$ are composite numbers?
1
vote
1answer
150 views
How to prove these two ways give the same numbers?
How to prove these two ways give the same numbers?
Way 1:
...
3
votes
4answers
171 views
Show y is odd in the equation $y^3 =x^2 +2$
Found a question which asks you to find all integer solutions $y^3 =x^2 +2$ . In order to do so, it first asks you to show that y is odd. How would one go about showing this?
Many Thanks
3
votes
1answer
59 views
Minimum number of coconuts
Three friends namely $A$, $B$ and $C$ collected coconuts with the help of monkey and fell asleep. At night, $A$ woke up and decided to have his share. He divided coconuts into three shares, gave the ...
2
votes
0answers
62 views
+50
Only 3 $n$ where $q=\left\lfloor (2 p_n+p_{n+2}) (p_{n}+p_{n+1}+p_{n+2})\over p_{n}\right\rfloor,\;\text{isPrime}(q)$?
Consider: $$q=\left\lfloor (2 p_n+p_{n+2}) (p_{n}+p_{n+1}+p_{n+2})\over p_{n}\right\rfloor,\;\text{isPrime}(q)$$
where $p_n$ denotes the $n$th prime.
Other than: $$n=6\quad\text{or}\quad ...
2
votes
1answer
57 views
Is this elementary number theory proof correct?
Let $A(n)$ be the number of primes less than $n$, divided by $n$ (so for example, $A(n) \leq 1$, as there cannot be more primes less than $n$ as there are integers less than $n$). Suppose that $n$ is ...
1
vote
1answer
54 views
Expressing $\sqrt{n +m\sqrt{k}}$
Following this answer, is there a simple rule for determining when:
$$\sqrt{n +m\sqrt{k}}$$
Where $n,m,k \in \mathbb{N}$, can be expressed as:
$$a + b\sqrt{k}$$
For some natural $a,b$?
This boils ...
3
votes
1answer
43 views
Knowing that $n= 3598057$ is a product of two different prime numbers and that 20779 a square root of $1$ mod $n$, find prime factorization of $n$.
Knowing that $n= 3598057$ is a product of two different prime numbers and that 20779 is a square root of $1$ mod $n$, find prime factorization of $n$.
What I have done so far:
$n = p \cdot q$
...
0
votes
2answers
101 views
RSA: Prove that all messages encrypt to itself
RSA: Prove that all messages encrypt to itself if $p=5$, $q=17$, $e=33$.
5
votes
2answers
104 views
Do there exist $29$ consecutive integers so that every of them has exactly $2$ distinct prime factors?
Do there exist $29$ consecutive integers, denote $a,a+1,\cdots,a+28$, so that every of them has exactly $2$ distinct prime factors?
For example, $25$ has only one distinct prime factor, and $30$ ...
3
votes
1answer
58 views
How to prove the existence of infinitely many $n$ in $\mathbb{N}$,such that $(n^2+k)|n!$
Show there exist infinitely many $n$ $\in \mathbb{N}$,such that
$(n^2+k)|n!$ and $k\in N$
I have a similar problem:
Show that there are infinitely many $n \in \mathbb{N}$,such that
...
6
votes
3answers
145 views
Show that the only solution to $\phi(n) =n-2$ is $n=4$
Came across this question in Number Theory.
Let $\phi$ denote Euler's totient function; Show that the only
solution to $\phi(n) =n-2$ is $n=4$
My workings so far have included, firstly ...
2
votes
1answer
42 views
How to prove the existence of odd numbers $a$ and $b$ in $2m\equiv a^{20}+b^{11}\pmod{2^n}$
Show that for any natural numbers $m,n$, there exist odd numbers $a,b$ such that
$$2m\equiv a^{20}+b^{11}\pmod{2^n}$$
Thank you everyone.
4
votes
2answers
44 views
positive Integer value of $n$ for which $2005$ divides $n^2+n+1$
How Can I calculate positive Integer value of $n$ for which $2005$
divides $n^2+n+1$
My try:: $2005 = 5 \times 401$
means $n^2+n+1$ must be a multiple of $5$ or multiple of $401$
because ...
1
vote
1answer
50 views
Legendre symbol proof
Show that if $a$ is a quadratic residue of the odd prime $p$, then the solutions of $x^2\equiv{a}\pmod {p}$ are $x\equiv{\pm a^{n+1}}\pmod {p}$ if
$p=4n+3$.
Proof
Assume $p=4n+3$ and ...
0
votes
3answers
137 views
Can countability coexist with infinity?
This question concerns the countability of the real numbers.
First I will show how I count the numbers between 0 and 1 on the real line.
It is done by reversing digits behind the coma, so
that e.g. ...
3
votes
2answers
23 views
Number of Solutions for Congruency Equations
I'm leaning congruency equations, so for example:
$$
ax \equiv b \pmod m
$$
I have that the number of solutions will be equal to $d$, where
$$
d = \gcd(a, m).
$$
And the solutions ae:
$$
...
2
votes
1answer
40 views
A trigonometric identity for special angles
Prove that for a natural number $n$,
$$\prod_{k=1}^n \tan\left(\frac{k\pi}{2n+1}\right) = 2^n \prod_{k=1}^n \sin\left(\frac{k\pi}{2n+1}\right)=\sqrt{2n+1}.$$
3
votes
0answers
52 views
On Sixth Powers $x_1^6+x_2^6+\dots+x_6^6 = z^6$
Fourteen years ago, in 1999 (has it been that long?) Merignac started a search for,
$$x_1^6+x_2^6+\dots+x_6^6 = z^6$$
using the five congruence classes,
$$\begin{aligned}
...
1
vote
1answer
20 views
Determining whether a quadratic congruence is solvable using Legendre symbol
I'm trying to detect whether the quadratic congruence $2x^2 + 5x - 9$ is congruent to $0$ modulo $101$. I've think I'll be able to detect whether there is or there is no solution using Legendre ...
0
votes
2answers
33 views
Odditiy: An Analysis of Skew-Symmetric $n\times n$ Matrices
Let $A \in M_{n×n}(\mathbb{R})$ be a skew-symmetric matrix, i.e., $A^t = −A$. Prove that if $n$ is odd, then $\det{A} = 0$.
2
votes
2answers
61 views
Proving two equations involving the greatest common divisor
Show or prove that $$\gcd \left(\frac{a^{2m}-1}{a+1} ,a + 1\right )=\gcd(a + 1 , 2m),$$
and that
$$\gcd \left(\frac{a^{2m + 1}+1}{a+1} , a + 1\right)=\gcd(a + 1 , 2m + 1).$$
2
votes
1answer
26 views
Cyclic shifts when multiplied by $2$.
I was trying to solve the following problem:
Find a number in base $10$, which when multiplied by $2$, results in a number which is a cyclic shift of the original number, such that the last digit ...
1
vote
1answer
26 views
Modulus Cancellation Law
I'm trying to understand the proof for cancellation law in modulus which states that:
...
3
votes
1answer
70 views
Why is $n=\frac{2p^2+2pq+2pr+q^2+2qr+r^2}{p+q+r}$, where $n$ is $\text{prime}$, of form such that $p\pm a,p\pm b,$ are $ \text{prime}, 1<a<b<n$
Why is $n= \left\lfloor \frac{2p^2+2pq+2pr+q^2+2qr+r^2}{p+q+r} \right\rfloor$, where $n$ is $\text{prime}$, of form such that $p\pm a,p\pm b,$ are $ \text{prime}, 1<a<b<n$?
Consider this:
...
1
vote
1answer
31 views
Lengendre symbol calculation
I'm trying to calculate the lengendre symbol of (3/383) without using the Quadratic Reciprocity Law, and with not much success.
I've thought about checking if 2^191 is congroent to 1 modulo 383 but it ...
4
votes
4answers
75 views
Prove or disprove the following statements involving greatest common divisor
Help with prove or disproving either of these statements would be really appreciated, one or the other is fine, I just need a start or a solution to one and I'm sure I could probably figure the other ...
16
votes
1answer
136 views
To prove that $2^{3n}+2^n +1$ is not a perfect square.
Question: Prove that $2^{3n} + 2^n + 1$ cannot be a perfect square for any natural $n$.
I attempted this question and failed in two different ways.
1) I considered a polynomial $p(x) = x^3+ x + 1 - ...
0
votes
1answer
42 views
Why is $\{n=4r+1,r = {n-1\over 2}\}\subset \mathbb{P}$ true under these conditions?
Let $p=p_k$, $q=p_{k+1}$ and $r=p_{k+2}$, where $p_m$ denotes the $m$th prime.
I conjecture that whenever $n$ is prime, where $n$ is defined as follows:
$$n = 1+\left(\left\lfloor{p\over ...
