Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.
0
votes
3answers
57 views
Mathematical Induction prime help
I recently obtained "What is Mathematics?" by Richard Courant and I am having trouble understanding what is happening with the Prime Number Unique Factor Composition Proof (found on Page 23).
The ...
0
votes
3answers
51 views
Finding the number of integer solutions, why is this wrong?
The question is to find the number of solutions such that $(x, y)$ are integers: $(x-8)(x-10)=2^y$. Here's what I did: $u(u-2)=2^y$. From the quadratic formula, $u=1+\sqrt{1+2^y}$. This is where I ...
1
vote
2answers
33 views
Solve the following Linear Congruences
Solve the following Linear Congruences:
$$x\equiv 4\pmod {12}$$
$$x\equiv 7\pmod {21}$$
$$x\equiv 10\pmod {15}$$
2
votes
2answers
29 views
Factorials and Divisibility
I'm having trouble getting started on the following:
Given $n_1, n_2, ..., n_k \in$ $\Bbb N$, show that $n_1!\cdot n_2!\cdot\cdot\cdot n_k! |(n_1+n_2+...+ n_k)!$
I thought about a proof by ...
1
vote
2answers
61 views
If $x$ and $y$ are in this given sequence, can $2^x+2^y+1$ be prime?
The sequence:
$3, 11, 13, 17, 19, 29, 37, 41, 53, 59, 61, 67, 83, 97, 101, 107, 113, 131, 137, 139, 149, 163, 173, 179, 181, 193, 197, 211, 227, 257, 269, 281, 293, 313, 317, 347, 349, 353, 373, 379, ...
2
votes
0answers
39 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 ...
7
votes
1answer
60 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 curiosities,
$$12^2+33^2 = 1233$$
$$88^2+33^2 = 8833$$
or, in ...
-7
votes
1answer
43 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
30 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
41 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
33 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
74 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
57 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
64 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
68 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
32 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
0answers
135 views
+50
Can an odd perfect number be divisible by $165$?
I know that an odd perfect number cannot be divisible by $105$ or $825$. I wonder if that's also the case for $165$ (this is actually a stronger statement).
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
31 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
70 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
82 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
34 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
44 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
70 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..
21
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
558 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
40 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
87 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
52 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: ...
