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

learn more… | top users | synonyms

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

$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
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: ...

1 2 3 4 5 70