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

learn more… | top users | synonyms

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

$48^{322} \pmod{25}$

How do I find $48^{322} \pmod{25}$?
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\\ ...

1 2 3 4 5 70