Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.
1
vote
2answers
42 views
Proving x and y is divisible by p (prime).
If p is a prime number and x and y are integers, how do I prove "if xy and x+y are both divisible by p, then x and y is divisible by p"?
I started like this..
1) p divides xy, so p divides x or p ...
3
votes
2answers
58 views
How to show: if $b \mid a$ and $c \mid a$ and $\mathrm{gcd}(b,c) = 1$, then $bc \mid a$?
A little stumped on this problem, any help would be greatly appreciated.
Show that for all $a,b,c \in \mathbb{Z}$, if $b \mid a$ and $c \mid a$ and $\mathrm{gcd}(b,c) = 1$, then $bc \mid a$.
0
votes
1answer
18 views
Counting couples of numbers
I have no trouble believing that, if $|n| \leq J$, then $$\#\{ (j_1,j_2) \in \{ 1,...,J \} \, | \, j_1-j_2 = n \} = J-|n|,$$
but can anyone explain it a little more formally?
Thank you in advance ...
2
votes
0answers
126 views
primes of the form $p=8k+1, 8k+3$ can be expressed as $p=a^2+2b^2$
I have trouble showing that primes of the form $p=8k+1, 8k+3$ can be expressed as $p=a^2+2b^2$.
Thanks in advance.
1
vote
0answers
38 views
Revised: Primes of form $p \equiv m \in S \mod x \ $
Refer to this question for background.
I was speculating if there was an elegant way to define sequences
A007645,A002313,A045357,A045407,A042986,A045331,
A045425,A045374,A045400,A045350,A042988;
...
6
votes
1answer
87 views
If an integer $n$ is such that $7n$ is the form $a^2 + 3b^2$, prove that $n$ is also of that form.
If an integer $n$ is such that $7n$ is the form $a^2 + 3b^2$, prove that $n$ is also of that form.
I thought that looking at quad residues mod $7$ might??? help. But that didn't take me anywhere so ...
4
votes
2answers
89 views
Find the greatest integer $k$ for which $1991^k$ divides $1990^{{1991}^{1992}}+1992^{{1991}^{1990}}$
Find the greatest integer $k$ for which $1991^k$ divides $$1990^{{1991}^{1992}}+1992^{{1991}^{1990}}$$
It is easy to see that $k \geq 1$ as $1990 \equiv -1$ and $1992 \equiv 1 \pmod{1991}$
Also, I ...
4
votes
3answers
47 views
Infinitely many primes of the form $4n+3$
I've found at least 3 other posts$^*$ regarding this theorem, but the posts don't address the issues that I have.
Below is a proof that for infinitely many primes of the form $4n+3$, there's a few ...
1
vote
1answer
78 views
Number array divided into several parts, genelize $a>b>c>d>0$ so $ab+cd>ac+bd$ to more numbers
Now, we have an original number array: $$a_1 > a_2 > a_3 > ... > a_{mn} > 0$$, I wonder whether the following inequality is the truth, if so, could you give me the proof or some ...
2
votes
1answer
47 views
Prove that $n^2 \leq \frac{c^n+c^{-n}-2}{c+c^{-1}-2}$.
Let $c \not= 1$ be a real positive number, and let $n$ be a positive integer.
Prove that $$n^2 \leq \frac{c^n+c^{-n}-2}{c+c^{-1}-2}.$$
My initial thought was to try and induct on $n$, but the ...
1
vote
1answer
53 views
Regarding definition of cuban primes
While considering the relationship between $6n-1$ (OEIS A002476) and generalized cuban primes(OEIS A007645) I came across something I thought was interesting:
Seems like the description of ...
0
votes
1answer
49 views
Generating primes from other primes
For a natural number $n$ let $M$ be an $n$ by $n$ matrix w/$0$'s on diagonal and natural numbers off diagonal and let $p_1, p_2, \dots, p_n$ be a set of prime numbers.
Note then, that
...
4
votes
3answers
327 views
The last 2 digits of $7^{7^{7^7}}$
What is the calculation way to find out the last $2$ digits of $7^{7^{7^7}}$? WolframAlpha shows $...43$.
1
vote
2answers
35 views
Quick way to solve computational congruences
The specific problem at hand is $$34x \equiv 60 \bmod{98}$$
I reduced to get $$17x \equiv 30 \bmod{49}$$
and from this I have
$$17x \equiv 30 \bmod{7}$$
which is easy to solve and yields $x \equiv 3 ...
0
votes
2answers
41 views
divisibility observation in particular patterns
Please look at the following observation made by trial and error method.
Let us take some 2-digit numbers like 12, 15, 24,...
12 = 1 * 2 = 2 => 2|12 (2 divides 12)
15 = 1 * 5 = 5 => 5|15
for 3 ...
1
vote
1answer
62 views
GCD of elementary symmetric functions
It is easy to show that p/ $\sigma_j$ ( where $\sigma_j$ is the sum of all products of j distinct members of the set {1,2,...,p-1}) for all $1 \leq j \leq p-2$, but how would you go about showing that ...
2
votes
1answer
65 views
Total no. of ordered pairs $(x,y)$ in $x^2-y^2=2013$
Total no. of ordered pairs $(x,y)$ which satisfy $x^2-y^2=2013$
My try:: $(x-y).(x+y) = 3 \times 11 \times 61$
If we Calculate for positive integers Then $(x-y).(x+y)=1.2013 = 3 .671=11.183=61.33$
...
5
votes
2answers
81 views
Number Theory: $x^2+y^2=a^2$
Is there a coprime triple $(x,y,z)$ such that $x^2+y^2=a^2, x^2+z^2=b^2, y^2+z^2=c^2$, where $a,b,c$ are integers
P.S. such solution doesn't exist for $a,b,c<1000$, as the computer says
P.P.S. ...
0
votes
0answers
93 views
Evaluating a polynomial at a root of unity?
Let $R = \mathbb{Z}[x]/(x^n+1)$ be the $2n$th cyclotomic ring (for $n$ a power of $2$ in which case $\Phi_{2n}(x) = x^n+1$). Let $g$ be an $n$-dimensional vector chosen at random from $\mathbb{Z}^n$ ...
1
vote
2answers
43 views
Classify the odd primes $q$ such that a NEGATIVE number is a quadratic residue $\mod{q}$
Suppose we are given $y < -1$. I wish to classify all primes $q$ such that $y$ is a quadratic residue $\pmod{q}$, i.e. such that there exists a number $x$ satisfying $$y \equiv x^2 \pmod{q}.$$
How ...
2
votes
1answer
50 views
Finding a prime $p$ to solve a quadratic congruence $\pmod{p}$
I have a congruence of the form $$ax^2+bx \equiv -1 \pmod{p},$$
where $p$ is an odd prime and $a,b \in \mathbb{Z}$. Given $a$ and $b$, is there a general method to finding $p$ such that the above ...
8
votes
2answers
147 views
Compute the remainder when $67!$ is divided by $71$.
This is how far I've been able to get.
By using Wilson's Theorem:
$$\begin{align}
70! &\equiv -1 \pmod{71} \\
67!(68)(69)(70) &\equiv -1 \pmod{71} \\
67!(68)(69)(-1) &\equiv -1 \pmod{71} ...
1
vote
1answer
84 views
Pell's type equation in sum
I have an another observation on concatenation in sum. For instance, take $12^2 + 33^2 = 1233$. Find as many such pairs (x, y) with $x^2 + y^2 = xy\,$(here xy is concatenation)is possible. Also, ...
-2
votes
2answers
61 views
Use the modular exponentiation algorithm to find $13^{277} \pmod {645}$
I need to solve this question using the modular exponentiation method.
3
votes
1answer
52 views
$\sigma(\sigma(p^2)) \neq 2p^2$ for all odd primes $p$.
How to prove that $\sigma(\sigma(p^2)) \neq 2p^2$ for all odd primes $p$?
I know that $\sigma(p^2)=1+p+p^2$ but I can't progress anymore.
0
votes
1answer
31 views
Using Fermat's little theorem to prove that $\sum_{i=0}^{n-3} (-1)^{i}a^{n-2-i}b^{i+1} = 1 + $ multiple of $n$
Using Fermat's little theorem, prove that
$$ a^{n-2}b - a^{n-3}b^2 + a^{n-4}b^4 - \ldots + ab^{n-2} = 1 + M(n) $$
if $n$ is prime and doesn't divide $a$, $b$ or $a+b$ and $M(n)$ means a ...
2
votes
3answers
141 views
$2^n-3^m=1 , m,n \in \mathbb N =?$
$2^n-3^m=1 , m,n \in \mathbb N =?$ my questions are:
do m,n exist?
are they finitely many $m,n$?
if there are infinitely many is there a way to describe them all?
Same question about $3^n-2^m=1 $, ...
-4
votes
0answers
38 views
may be too small but interesting…on triplets
In triplets, we can express one square is some of squares of other two positive numbers. Now, for positive numbers (a, b, c) the following is true.
a^2 + b^2 is not equal to c^2 for c < or = 6. ...
1
vote
1answer
63 views
$xy= z^2$ and $x, y$ are individual squares
We know that concatenation of $xy = z^2$ for $x = 4^2 = 16$ and $y = 3^2 = 9$. Here $169 = 13^2 \implies z = 13$. Now my question is how to prove this is the first such set of positive integers $(x, ...
5
votes
4answers
114 views
Using $\gcd(a,b)$ to find gcd of other values $\gcd(a^2,b)$ and $\gcd(a^3,b)$
If $\gcd(a,b) = p$, a prime, what are the possible values of $\gcd(a^2,b)$ and $\gcd(a^3,b)$?
Through examples I've been able to find the answer, but I don't know how to come up with a proof.
...
1
vote
2answers
39 views
GCD and divisibility
Update: I think there was a typo in the text. Please don't waste your time with this problem. :)
If gcd$(a,b) = p$, a prime, then $p|am$ and $p|an$ such that gcd$(m,n) = 1$
Why does gcd$(m,n)$ have ...
3
votes
3answers
77 views
Sum of two squares in a $\Bbb Z/p\Bbb Z$
I need to show that every element in $\Bbb Z/p\Bbb Z$ can be written as a sum of two squares. The case $p=2$ is trivial and $0$ is always $0^2 + 0^2$. So all I have to do is show that every element of ...
0
votes
1answer
34 views
Hyperbola from Pell's equation
Could you please explain the proof of finding infinitely many solutions are existing for $a^2 - 10b^2 = 1$ or $4$ or $9$. Also, discuss, is there any relation between hyperbola and Pell's equation? If ...
4
votes
3answers
59 views
Proving that if $n$ is odd and $\gcd(m, n) = 1$, then $\gcd(2m + n, 2n) = 1$
I've been trying to crack this one for the last little while. I've tried a few approaches, but none have bore any fruit.
Let $n > 0$ be an odd integer. Prove that if $\gcd(m, n) = 1$, then ...
7
votes
4answers
158 views
Connection between number theory and abstract algebra
I haven't taken abstract algebra yet but I was curious on what connections do number theory and abstract algebra share? Do the proofs of things like Fermat`s little theorem, the law of quadratic ...
2
votes
2answers
36 views
Is the sum of two coprime numbers also coprime to its summands?
I was comparing the statement of the ABC conjecture on Wikipedia to an article I found geared towards laymen. The propositions differ slightly, but they would be equivalent if the following were true:
...
1
vote
1answer
57 views
how to prove $f$ is an arithmetic function with this property $\sum_{d\mid n} f(d)=n^2$
how to prove $f$ is an arithmetic function with this property
$$\sum_{d\mid n} f(d)=n^2$$
Arithmetic function
10
votes
5answers
140 views
Prove that there are infinitely many natural numbers $n$, such that $n(n+1)$ can be expressed as sum of two positive squares in two distinct ways.
Prove that there are infinitely many natural numbers $n$, such that $n(n+1)$ can be expressed as sum of two positive squares in two distinct ways.($a^2+b^2$, is same $b^2+a^2$), $n \in \mathbb{N}.$
...
1
vote
1answer
75 views
Showing that $45083 $is prime
The question is:
Does $\;x^2 + 10x + 15 = 0\pmod{45083}\;$ have a solution?
I can rearrange this to $(x+5)^2 = 10\pmod {45083} \;$ so if I can show that $10$ has a square root mod 45083, I'm done.
...
0
votes
1answer
28 views
Formula for difference between two numbers on a wall clock in clokwise direction
It's my first post in math.stackexchange.com.
I got a necessity to find out the clockwise difference between two numbers on a wall clock. For example, difference between 12 and 1 is 1 where as the ...
2
votes
2answers
35 views
$\sum_{d\mid n} \frac{\mu^2(d)}{d} =\prod_{p|n} \left(1+\frac{1}{p}\right)$
how to prove:
$$\sum_{d\mid n} \frac{\mu^2(d)}{d} =\prod_{p|n} \left(1+\frac{1}{p}\right)$$
$\mu : \Bbb N\rightarrow \Bbb R$
$\mu(1)=1$
$ \mu(n)=
\begin{cases}
0 &,\;\;\; \text{if $\,n\,$ is ...
2
votes
1answer
52 views
how to find $n| 3^n+1$
this a problem in:
Waclaw Sierpinski 250 problems in elementary number theory 1971
if $n\in \Bbb N , n \gt1$ ,how to find :
$$n\mid3^n+1$$
the solution of book is :
There is only one such odd ...
2
votes
1answer
90 views
$xy$ itself square in this particular logic
I would like to know the solution or procedure to find the exact analysis/solution of one of my observation. let $x = a^2$ and $y = b^2$, then can we express $xy$ (concatenation of $x$ and $y$) as ...
7
votes
2answers
159 views
How to prove $n$ is prime?
Let $n \gt 1$ and
$$\left\lfloor\frac n 1\right\rfloor + \left\lfloor\frac n2\right\rfloor + \ldots + \left\lfloor\frac n n\right\rfloor = \left\lfloor\frac{n-1}{1}\right\rfloor + ...
0
votes
3answers
51 views
Solutions over $\mathbb{Z}_p$
What does this fact mean:
"the polynomial $\sum_{i=0}^{n}a_{i}x^{i}$ has at most $n$ solutions over $\mathbb{Z}_{p}$"
?
Thanks in advance,
Yaron.
3
votes
1answer
34 views
$\mathbb{Z}/m\mathbb{Z}$: A Complete Set of Representatives
So, I'm letting ${\scr{A}}=\{a_1,\dots,a_n\}$ be a complete set of representatives (C.S.R.) for $\mathbb{Z}/m\mathbb{Z}$. I'm considering all $b\in \mathbb{Z}$ and seeing if ${\scr{B}}=\{a_1+b, a_2+b, ...
1
vote
4answers
60 views
$[4]_{17}[x]_{17} = [2]_{17}$: How to optimally solve this equality.
This notation is found in Concrete Introduction to Higher Algebra.
Here is my method:
For something like $[3]_{11}[x]_{11}^2=[4]_{11}$ I've just been using C++ code like this:
...
3
votes
1answer
65 views
How do you calculate $25^{11} \pmod{341}$?
How do you calculate $25^{11} \pmod{341}$?
I understand you have to split the exponent into $11 = 1 + 2 + 8$?
2
votes
1answer
49 views
The set of exponential primes
Consider a set of integers $Q$ such that the set of all positive integers $\mathbb{Z}$ is equivalent to the span of ever possible power tower
$$a_1^{a_2^{\ldots a_N}}$$ involving $a_i \in Q$.
In ...
4
votes
4answers
198 views
How do you calculate the modulo of a really high number with a large power, with a really high mod number?
I need to work out $516489222^{22} \pmod{96899}$. I know there are easier ways of working this out, but am really struggling.
