Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.
2
votes
0answers
32 views
Search for a counterexample for a Pell’s equation conjecture
Let the constant $d$ in Pell’s equation $x^2-dy^2=1$ be a prime such that $d=n(n+1)(n+2)+1$.
Now compare the - lowest - solution for $d$ and $d-1$. My conjecture is that the solution for $d$ is much ...
4
votes
1answer
43 views
Fermat primes and the equation $x^2+y^2 = 10^n x+y$
This is related to the question by Naroza which was ably answered by E. Wong. In a nutshell, it seeks to find more examples of the curiosity,
$$12^2+33^2 = 1233$$
or, in general, to solve,
...
-7
votes
1answer
40 views
RSA Encryption/Decryption (soft)
Let $m=3337$, $e=11$, $d=1171$. Encode and decode the message NO using the following known methods:
I've encoded messages as in Example 1 (above), but I don't know where to start on how to encode ...
0
votes
4answers
29 views
Correlation between multiplied numbers?
I do not have a strong math background, but I'm curious as to what this pattern is from a mathematical standpoint.
I was curious how many minutes there were in a day, so I said "24*6=144, add a 0, ...
3
votes
2answers
40 views
Primality test based on initial conditions alone.
Let $m=252601$. Suppose we discover that
$$3^{126300} ≡ 67772 \pmod{252601}$$
$$3^{252600} ≡ 1\pmod{252601}$$
Is then $252601$ prime? composite? Or can we not decide for sure from the information ...
0
votes
0answers
30 views
Proving that $\mathbb{Z}^*_{p^{k}}$ is cyclic
While proving that $\mathbb{Z}^*_{p^{k}}$ is cyclic for an odd prime $p$, we assume by hypothesis that $\mathbb{Z}^*_{p^{k}}$ is cyclic
and generated by some element g.
Also by hypothesis, each ...
2
votes
2answers
73 views
What is the least nonnegative number $a$ congruent to $3^{340}\pmod{341}$?
Find the least nonnegative number $a$ congruent to $3^{340} \pmod{341}$.
What steps should I take to get to the answer?
3
votes
1answer
54 views
How many solutions does this equation have $x^2 \equiv 1017 (\mod 2^k)$
How many solutions does this equation have $x^2 \equiv 1017 \ \mod 2^k$?
I know that $1017 \equiv 1 \mod 8$?
I think that for $k=1$ we have $x^2 \equiv 1017 \mod 2$ and the solution is $x=1 \mod 2$
...
2
votes
3answers
57 views
Let $n$ be an odd integer greater than 1. Show that one of the numbers $2^1-1,2^2-1,…,2^n-1$ is divisible by $n$.
Let $n$ be an odd integer greater than 1. Show that one of the numbers $2^1-1,2^2-1,...,2^n-1$ is divisible by $n$.
I know that pigeonhole principle would be helpful, but how should I apply it? ...
1
vote
2answers
33 views
general solution of equation and relation
I am interested in learning the below question in some elementary way. Please discuss this problem and help me to get mind free state.
How to get solutions for $x^2 - 10y^2$ = $1$? I would like to ...
4
votes
1answer
65 views
Sum equal to the product
I know that $2 + 2 = 2 \cdot 2$ and $1 + 2 + 3 = 1 \cdot 2 \cdot 3.$
My question: Are there other positive integers with sum equal to the product? (The number 1 can not appear more than once among ...
2
votes
1answer
33 views
True or false statements
Two of the following statements are true and one is false
a) For all rational numbers $q$, there exists an integer $n$ so that $q+n=271$.
b) For all integers $n$, there exists a rational ...
1
vote
1answer
42 views
REVISTED$^1$ - Order: Modular Arithmetic
Relevant Literature:
Question:
Observe that $2^{10}=1024≡−1 \pmod{25}$.Find the order of $2$ modulo $25$.
Thoughts:
Direct answers are OK, but I'd like to know if I'm right that what I'm really ...
0
votes
1answer
31 views
Which numbers of [0,1) have a unique base g expansion?
Good evening,
i know that is question is rather standard, but unfornunately I have not much knowledge of number theory.
Take $2 \leq g\in \mathbb{N}$. I know that every $x \in [0,1)$ can be ...
0
votes
2answers
107 views
A proof of $n*0=0$?
The only proof I've seen for this assumes that $0$ follows all the rules of arithmetic. How can we make that assumption when dividing by $0$ is a problem? I know that some people don't agree that all ...
4
votes
3answers
55 views
0
votes
0answers
15 views
A map $M_k(\Gamma(N))\to M_k(SL(2,\mathbb{Z})$?
Is there a natural map $M_k(\Gamma(N))\to M_k(SL(2,\mathbb{Z})$? If so, what is a good reference to read about it?
The moduli interpretation of level $N$ forms is as functions on pairs of the form ...
0
votes
0answers
29 views
A conjecture about mersenne primes and non-primes
The presented conjecture emanates from a generalization of the 4 button riddle, reported on a (Wu’s) riddle site: (You are trapped in a small phone booth shaped room. In the middle of each side of the ...
2
votes
4answers
60 views
$\sum_{k=1}^n m(k)$, where $m(k)$ is defined by $2^{m(k)} || k$.
I'm looking at the sum:
$$f(n) = \sum_{k=1}^n m(k),$$
where $m(k)$ is defined by $2^{m(k)} || k$, i.e. $2^{m(k)}$ is the largest power of $2$ that divides $k$. For example, we have $f(8) = ...
4
votes
1answer
81 views
Eratosthenes-like sieve - infinitely many left unstruck?
Given any infinite sequence $c_1,c_2...$ of natural numbers, if all of the natural numbers $x$ such that there exists $n$ such that $x\equiv c_n (\mod p_n)$ and $x \geq 2p$, where $p_n$ is the nth ...
0
votes
1answer
25 views
Why does $3+ (-1)\left(\left\lfloor\sum_{k=1}^{|\{x\in P,\;x\le n\}|} \frac{P_k}{1-P_k}\right\rfloor\right) = \pi(n),\quad n\ge1223$?
Let $P$ denote $\text{primes}$, and $\pi(x)$ denote $|P| \le x$.
Here's my first question: Why does
$$3+ (-1)\left(\left\lfloor\sum_{k=1}^{|\{x\in P,\;x\le n\}|} ...
9
votes
1answer
142 views
Show that $4mn-m-n$ can never be a square
Let $m$ and $n$ be positive integers. Show that $$4mn-m-n$$ can never be a square.
In my attempt I started by assuming for the sake of contradiction that $$4mn-m-n=k^2$$ for some $k \in ...
2
votes
1answer
33 views
What is the terminology for the non-repeating portion of a rational decimal?
Given a number co-prime with 10, such as thirteen, we can construct a repeating decimal from its reciprocal: $\frac{1}{13}$ = 0.(076923). If we successively divide this number by a factor of 10 (i.e., ...
3
votes
0answers
56 views
Divisibility of an expression involving the Möbius function
Let $d$ and $n$ be integers, with $n\geq 2$, and define $$R(n,d) := \sum_{k\mid n} \mu( n/k)d^k,$$ where $\mu$ is the Möbius function. It can be shown (see below for an arithmetic proof) that $n\mid ...
4
votes
1answer
45 views
What is the largest number such that the number formed by the first $n$ digits is divisible by $n$?
What is the largest number such that the number formed by the first $n$ digits is divisible by $n$?
For example, if we have a number $$abcdefghijklm,$$ and all of these leters stand for digits,
then ...
1
vote
1answer
36 views
RSA encryption theory - modulo theory
I'm a bit mathematically challenged and have been working on the RSA cipher (good start). I can find the public and private keys and know how to work do modulo operations on a calculator. The problem ...
2
votes
1answer
65 views
Find the first non-prime
Find the first non-prime $x(d)$ in Pell’s equation using the procedure below.
For every prime number $p$, construct a (possibly empty) series of natural numbers using the following procedure (start ...
1
vote
3answers
69 views
If $x^2\equiv 1 \pmod{n}$ and $x \not\equiv \pm 1 \pmod{n}$, then either $\gcd(x-1,n)$ or $\gcd(x+1,n)$ is a nontrivial factor of n
I'm reading elementary number theory and trying to understand the following problem: If $x^2\equiv 1 \pmod{n}$, $n=pq$, $p$ and $q$ are odd primes and $x \not\equiv \pm 1 \pmod{n}$, then either ...
0
votes
2answers
43 views
squares of integers, and multiples of 4
Prove that for all $n\in\Bbb Z$ there exists $k\in\Bbb Z$ such that either $n^2=4k$ for $n^2 = 4k + 1$.
A hint given was: What are the possible remainders for n after dividing by 4? Break into ...
3
votes
2answers
69 views
Proving that there are infinitely many prime numbers of the form $4k+3$
Anyone wanna help me solve this one? Been at it for a little bit but haven't really gotten anywhere..
20
votes
3answers
2k views
Yitang Zhang: Prime Gaps
Has anybody read Yitang Zhang's paper on prime gaps? Wired reports "$70$ million" at most, but I was wondering if the number was actually more specific.
EDIT$^1$:
Are there any experts here who can ...
2
votes
2answers
46 views
Number of solutions to $x^k \equiv h \pmod {q^n}$
Could someone please give me a hint/solution to
the question, say $q$ is a prime and $(q,h)=1$, then
$$
x^k \equiv h \pmod {q^n}
$$
has at most $k$ solutions $1 \leq x < q^n$?
Thanks!
1
vote
3answers
68 views
showing that the Euler's number is irrational
Our teacher wants us to do the following:
Suppose that e is rational i. e $e=\frac{a}{b}$ where $a,b\in\mathbb{N}$. Choose $n\in\mathbb{N}$ such that $n>b$ and $n>3$. Use the following ...
25
votes
4answers
556 views
About the property of $m$: if $n < m$ is co-prime to $m$, then $n$ is prime [duplicate]
The number $30$ has a curious property:
All numbers co-prime to it, which are between $1$ and $30$ (non-inclusive) are all prime numbers!
I tried searching(limited search, of course) for numbers ...
2
votes
2answers
33 views
Show that 7 is a quadratic residue for any prime p of the form 28k + 1 and 28k + 3.
Interesting number theory question, which I feel should be reasonably straight forward, but I can't seem to crack it.
Show that 7 is a quadratic residue for any prime p of the form 28k + 1 and 28k ...
0
votes
1answer
39 views
RSA cryptosystem: If $k$ is a multiple of $\phi(N)$, then $k=2^t r$ with $r$ odd and $t\geq1$
I'm reading Twenty Years of Attacks on the RSA Cryptosystem by Dan Boneh and trying to understand the proof of the Fact 1 on page 3.
Fact 1: Let $(N,e)$ be an RSA public key. Given the private ...
2
votes
3answers
62 views
Show that no number of the form 8k + 3 or 8k + 7 can be written in the form $a^2 +5b^2$
I'm studying for a number theory exam, and have got stuck on this question.
Show that no number of the form $8k + 3$ or $8k + 7$ can be written in the form $a^2 +5b^2$
I know that there is a ...
7
votes
2answers
84 views
The number of solutions of $ax^2+by^2\equiv 1\pmod{p}$ is $ p-(\frac{-ab}{p})$
What I need to show is that
For $\gcd(ab,p)=1$ and p is a prime,
the number of solutions of the equation $ax^2+by^2\equiv 1\pmod{p}$ is exactly $p-(\frac{-ab}{p})$.
I got a hint that I have to use ...
1
vote
2answers
58 views
$n$ divides $\phi(a^n -1)$ where $a, n$ are positive integer. [duplicate]
I need to show that $n$ divides $\phi(a^n -1)$ where $a, n$ are positive integer.
could any one give me a hint?
3
votes
4answers
116 views
Find $a,b,c \in \mathbb {Q}$
Find $a,b,c \in \mathbb {Q}$ such that:
$\left\{\begin{array}{rl} x^3&\in \mathbb Q \\ x&\notin \mathbb{Q}\\ ax^2+bx+c &=0\end{array}\right.$
I tried Vieta's formulas, but seem like it ...
2
votes
0answers
44 views
Playing with bases (2013 AMC 10B #25)
$N$ is a 3 digit positive integer. It can be represented in base 5 and base 6 as the strings $n_5$ and $n_6$. If we then treat $n_5$ and $n_6$ as the base 10 encodings of two integers $N_5$ and $N_6$, ...
2
votes
0answers
48 views
finding out linear decomposition of $x$ into $k$ prime numbers
Some $k$ prime numbers $n_1, n_2, ..., n_k$ are given. Then some natural number $x$ is provided.
Then we want to figure natural numbers (including zero) $m_1, m_2, ..., m_k$ so that $n_1m_1 + n_2m_2 ...
0
votes
3answers
51 views
Find integer solutions of $x^2 -px +q=0$, where $p$ and $q$ are prime
Quick number theory question that I have just come across, was wondering if anyone could shed some light on it.
So $p$ and $q$ are given to be prime numbers, and we are told that the equation $x^2 ...
4
votes
3answers
83 views
proving $n!>2^n\;\;\forall \;n≥4\;$ by mathematical induction
My teacher proved the following $n!>2^n\;\;\;\forall \;n≥4\;$ in the following way
Basis step: $\;\;4!=24>16$ ok
Induction hypothesis: $\;\;k!>2^k$
Induction step: ...
4
votes
3answers
80 views
How do you prove that the mean of the co-primes of a number is half the number?
Say $n = 6$, The set of co-primes is $\{1, 5\}$, $\text{mean} = 3$
For $n = 9$, the set of co-primes is $\{1, 2, 4, 5, 7, 8 \}, \text{mean} = 4.5$
Question: Prove that the mean of co-primes of ...
9
votes
1answer
233 views
Prime with digits reversed is prime?
Well, just another idea came up into my mind and i have no idea how to solve it :D
Is there infinitely many prime numbers, which are not repunits and their inverse is also prime? (For example, inverse ...
1
vote
2answers
34 views
If a number is a square modulo $n$, then it is also a square modulo any of $n$'s factors
Say we have $a \equiv x^2 \bmod n$. How would we prove that this implies:
$$\forall \text{ prime }p_i\text{ such that }\,p_i\mid n,\;\exists y\,\text{ such that }\, a \equiv y^2 \bmod p_i$$
2
votes
0answers
75 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
3answers
78 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
55 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\\
...
