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

learn more… | top users | synonyms (1)

5
votes
1answer
62 views

Is there a formula for $(\frac{3}{p})$?

In number theory we learn when $2$ is a quadratic residue: $ \left( \frac{2}{p}\right) = (-1)^{\frac{p^2 - 1}{8}}$ It takes a moment to verify that $\displaystyle \frac{p^2 - 1}{8} \in \mathbb{Z}$ ...
1
vote
1answer
33 views

construct a unit on $\mathbb{Z}[\sqrt[3]{7}]$?

how might I construct a unit on $\mathbb{Z}[\sqrt[3]{7}]$? Can it be done using pigeonhole principle as with square roots and Pell equation. I had been reading about the Voronoi continued fraction or ...
1
vote
2answers
46 views

Equation involving the Jacobi symbol: $\left( \frac {-6} p \right) = 1$?

I have to determine the values of $p \in \{0, \dots, 23 \}$ such that $\left( \frac {-6} p \right) = 1$. I have that: $$\left( \frac {-6} p \right) = \left( \frac 2 p \right) \left( \frac {-3} p \...
-1
votes
1answer
56 views

Given $N$ find the number of natural numbers less than $N$ that may be written in the form $\frac{(k)(k+1)}{2}$

Given $N$, find the number of natural numbers less than $N$ that may be written in the form $$\frac{k(k+1)}{2},$$ where $k\in \Bbb N$. I know that the answer to this problem is approximately $\sqrt {...
-1
votes
0answers
28 views

Confusion between Sequences and Number theoretic functions.

I've just started learning Number Theoretic function,the definition of ,Number Theoretic function,which i've just read created some confusion b/w Number Theoretic function & Sequences. The ...
6
votes
2answers
212 views

Find the $k$ such that $2^{(k-1)n+1}$ does not divide $\frac{(kn)!}{n!}$.

Find all positive integers $k$ such that for any positive integer $n$, $2^{(k-1)n+1}$ does not divide $\frac{(kn)!}{n!}$. From olympiad problem I'm curious So far no one to solve this problem,Maybe ...
1
vote
1answer
43 views

Is the difference between $ 2$ coprimes always either 1 or prime number?

If a and b are both positive and coprime with $a > b$, Is $a - b$ always either $1$ or prime number? Can $a - b$ be composite number?
0
votes
2answers
36 views

How to explain the rationality of a solution?

This an exercise from an elementary number theory textbook: "The curve $$y^2 = x^3 + 8$$ contains the points $(1, -3)$ and $(-7/4, 13/8)$. The line through these two points intersects the curve in ...
1
vote
1answer
85 views

Even Digit Series (2,4,6,8,20,…) [duplicate]

I have a series of numbers whose Nth term is a number whose all of the digits are even. The series is of course divergent , but i am interested in finding a formula to find the Nth term of this series....
4
votes
4answers
80 views

Showing that there are infinitely many integer solutions for the hyperbolic formula $|a^2 - 26 b^2| = 1$

I want to show that the formula $$ | a^2 - 26\cdot b^2| = 1$$ has infinitely many solutions $(a, b) \in \mathbb{Z}^2$. First I tried to solve the formula for one of the two variables, to get ...
2
votes
2answers
31 views

Use of greatest common divisor to calculate unknown

We have three numbers $x ,y, z$. If we know the values of $x$ and $z$ then is it correct to say that $y$ should be a multiple of $z/\gcd(z,x)$ for the expression shown below to be true? Here $\gcd$ ...
4
votes
0answers
67 views

Skiponacci: $p | a_p$ Alternate Solution

For the Skiponacci sequence: $a_0=3, a_1=0, a_2=2,$ and $a_{n+1}=a_{n-1}-a_{n-2}$ for $n>2$, prove that any prime $p$ divides $a_p$. Is there any alternate solution other than using ...
0
votes
1answer
42 views

Basic question with coprimes and modulos

I started reading about Modular Arithmetic and solving some random basic exercises, and this one appeared: "Find an integer number $a$ such that any $b$ coprime with 34 is congruent to $a^k \mod34$ ...
3
votes
2answers
61 views

Origin of Almost Perfect Numbers

Let $N$ be a positive integer. $N$ is called a perfect number if the sum of its positive divisors denoted by $\sigma(N)=2N$. For example $6$ is a perfect number since: $\sigma(N)=1+2+3+6=12=2(6)$. ...
0
votes
1answer
31 views

System of linear congruence when not relatively prime

I am new to Abstract Algebra and understand how to solve when the mods are relatively prime, but I am struggling when they aren't relatively prime. I have a system of of linear congruences that I ...
2
votes
2answers
71 views

If $d=\gcd\,(f(0),f(1),f(2),\cdots,f(n))$ then $d|f(x)$ for all $x \in \mathbb{Z}$

$\textbf{Question.}$ Let $f$ be a polynomial of degree $n$ which takes only integral values. If $d=\gcd\,\{f(0),f(1),f(2),\cdots,f(n)\}$ then show that $d|f(x)$ for all $x \in \mathbb{Z}$. How ...
1
vote
0answers
24 views

Analogy to Four Squares Theorem.

Is there a multivariate and univariate polynomial analogy to Lagrange's sum of four squares?
1
vote
1answer
36 views

Cyclic prime groups

can I have a refrence to an introduction (not super beginner level, one after) of the multiplicative group $Z/ZP$? I know that it is cyclic. I am interested in known properties of the generators. ...
1
vote
1answer
43 views

Succession in Peano axioms

In "Analysis I" - Herbert Amann states: "The natural numbers consist of a set $ N$ , a distinguished element $0\in N$ and a function $v:N\to N^*$ with the following properties: ($N0$) $v$ is ...
1
vote
2answers
35 views

Finding unknown numbers using $ LCM $ and $ HCF $

Find two numbers, $A$ and $B$, both smaller than $100$, that have a lowest common multiple of $450$ and a highest common factor of $15$. I know that this involves the formula of $A × B = LCM × HCF$ ...
0
votes
1answer
46 views

What am I missing in this induction proof?

Prove that if $g:\mathbb{N}\rightarrow \mathbb{N}$ and $\forall x,y\in \mathbb{N}, x<y\Rightarrow g(x)<g(y)$ then $n\leq g(n)\space\space\space \forall n\in \mathbb{N}$ My proof so far (...
6
votes
1answer
24 views

In general what happens in Conway's Prime Game given $2^n$, with $n$ composite, as the initial value?

The fractions are $$\frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{2}, \...
1
vote
1answer
47 views

Prove $(ah,bk)=(a,b)(h,k)\left(\frac{a}{(a,b)},\frac{k}{(h,k)}\right)\left(\frac{b}{(a,b)},\frac{h}{(h,k)}\right)$

I had an idea and was wondering if it works. I seem to have gotten away quite cheaply. The many multiplications on the right side made me consider the prime divisors: $p\mid (ah,bk)\Rightarrow p\mid ...
0
votes
1answer
57 views

What are the number of solutions of $x+y+z=r$ .By just giving the solutions as even/odd pairs?

In Detail:- I want to know that if I just consider odd/even then $x+y+z =r$ which having solutions $= (n+r-1)C(r-1)$ . But when we classify the numbers as just odd and even then there will be reduced ...
1
vote
2answers
50 views

How to prove that set of prime number such $p\equiv 7 [12]$ is infinite?

We have $n \ne 3k$ with $k\in \mathbb{N}$ and the integer $4n^2+3$. I think the first thing is to prove that this integer has a prime factor $p\equiv 7 [12]$. I don't have idea to begin. Thanks in ...
0
votes
0answers
31 views

A more elegant proof of $[(a,b),c]=([a,c],[b,c])$.

So assuming the fundamental theorem of arithmetic and using the definitions $(a,b)=\prod_i^{\infty}p_i^{\min\left\{a_i,b_i\right\}}$ and $[a,b]=\prod_i^{\infty}p_i^{\max\left\{a_i,b_i\right\}}$ with $...
4
votes
0answers
124 views

Diophantine equation with binomial coefficient

Suppose that $p$ is a prime number and $p \le q \le p^2$ is an integer. How many solutions are there to the following equation? $$\binom{p^2}{q}-\binom{q}{p}=1$$ This question was proposed ...
4
votes
5answers
171 views

Find $3^{333} + 7^{777}\pmod{ 50}$

As title say, I need to find remainder of these to numbers. I know that here is plenty of similar questions, but non of these gives me right explanation. I always get stuck at some point (mostly right ...
6
votes
0answers
74 views

Integer divisibility

Given a (not strictly) decreasing sequence of natural positive numbers $a_1, a_2, \dots, a_n$ prove that $$ \prod_{i<j} j-i \quad\big|\quad \prod_{i<j} a_i - a_j - i +j $$ I already know a ...
-1
votes
3answers
888 views

Find the first digit of a huge product in case of multiplication

Let there be many numbers $a_1,a_2,a_3,\dots,a_n$. I want to find the first digit of their product, i.e. of $A=a_1\times a_2\times a_3\times a_4\times \dots\times a_n$. These numbers are huge and ...
1
vote
1answer
36 views

Compute $(a_n,a_{n+1}) \forall n$ with $a_n$ the fibonacci sequence

Here my attempt: Employ the euclidean algorithm, i.e. $\forall r_0,r_1 \exists q,b: r_0 = q\cdot r_1+r_2, 0\le r_2 \lt r_1$. $q,b$ are determined uniquely. Since the definition of the fibonacci ...
0
votes
1answer
43 views

Help with finding the remainder of $2^{2^n}$ when divided by 13

I have this problem from an algebra course: Find the remainder of $2^{2^n}$ when divided by 13, $\forall n \in \Bbb N$ It's in a section of Fermat's little theorem and Chinese Remainder Theorem ...
1
vote
1answer
37 views

Compute $(a^{2^m}+1,a^{2^n}+1)$

I need your uncaring objective eyes. The hint for the problem was: show that for a given $m>n$ $A_n|A_m-2$. So here my attempt: $A_m-2=a^{2^m}-1$, additionally I can write $m=n+k$ and therefore I ...
0
votes
0answers
7 views

equivalent transformation of positive natural numbers

I have to argue, if the following equivalent transformations are generally valid for all positive natural numbers $n,m,N \in \mathbb N$ and $n,m,N \neq 0$: $$ n \cdot m \lt M n \lt N/m $$ $$ n/m \gt ...
1
vote
1answer
96 views

How to find $k$-th number whose digits are all even?

As my question says I have to find $k$-th number whose digits are all even. I figure out that all those numbers are made of of $\{0,2,4,6,8\}$ and there is a sequence in which the numbers change their ...
1
vote
0answers
31 views

Robin's theorem for Mersenne Numbers with Prime Exponent

The Robin's theorem states $\sigma(n)<e^\gamma n\ln\ln n$ for $n>5041$. For $n=2^q-1$, $q$ being prime and knowing that the divisors of $2^q-1$ are in the form $2kq+1$, is there a better bound ...
0
votes
5answers
66 views

Divisiblity of an expression by 3

Doing a bit of work and came across a result I believe to be true but am not sure how to prove. Haven't done much work at all in number theory so any help r tips would be great. "$2^{k+1}-1$ is ...
1
vote
3answers
51 views

Elementary number theory sum of divisors

Let the sum of the divisors of a number $N$ be equal to $s$(excluding N itself) then show that if $s=N$ then show that N is a perfect number. I tried to use the basic formula for sum of divisors but ...
3
votes
1answer
187 views

Show that $101!+1$ is not prime number [closed]

Show that $101!+1$ is not prime number. How many ways exist to do it?
0
votes
1answer
19 views

Prove that for any monic polynomial $f$ with integer coefficients, if $q$ is a (complex) root of $f$ and $p$ is a prime, then $f(q^p) = 0 \pmod p.$

Prove that for any monic polynomial $f$ with integer coefficients, if $q$ is a (complex) root of $f$ and $p$ is a prime, then $f(q^p) = 0 \pmod p.$ Can you provide a simple proof?
1
vote
1answer
16 views

Polynomial, pseudoprimes

1) By Fermat's Little Theorem , given a polynomial of the form $f(x) = x - c$, if $p$ is a prime, then the sum of the pth powers of the roots of f is congruent to the sum of the first powers $\pmod p)$...
1
vote
4answers
61 views

Elementary Number Theory exponents [duplicate]

How can one prove that the fifth power of any number has the unit digit same as that of the number itself. Actually the question was to prove that $n^5-n$ is divisible by $30$ when n is a number ...
2
votes
1answer
25 views

Elementary number theory (HCF)

$$X=a_1x+b_1y$$ $$Y=a_2x+b_2y$$ $$a_1 b_2-a_2b_1 =1$$ Then prove that the greatest common divisor of X and Y is same as that of x and y. Though we can easily see that this is normal equation ...
3
votes
1answer
64 views

Prove that if $a+b = y$, where $a \neq 1$ and $\gcd(a,b) = 1$;$ a^b+b = 1 (\mod y)$ then

Prove the following conjecture: If for two integers $a, b$: $a+b = y$, $a ≠ 1$, and $\gcd(a, b) =1$ $a^b+b$ $\equiv$ $1$$\pmod y$ $y$ is prime. (I am new here at math.stackexchange.com)
1
vote
1answer
38 views

Does this formula ${n^2+3n\over 2}+{2(n+1)(n+2)-1\over 2(n+1)(n+2)}$ generates Pythagorean triples for all n?

The idea came from this site another formula for generating Pythagoras Triples Let $n\ge1$ $2{11\over 12}, 5{23\over24}, 9{39\over 40},\cdots$ is generated from ${n^2+3n\over 2}+{2(n+1)(n+2)-1\over ...
2
votes
1answer
15 views

Let $a \in \Bbb Z$ such that $gcd(9a^{25}+10:280)=35$. Find the remainder of $a$ when divided by 70.

I'm stuck with this problem from my algebra class. We've recently been introduced to Fermat's little theorem and the Chinese Remainder Theorem. Let $a \in \Bbb Z$ such that $gcd(9a^{25}+10:280)=35$...
1
vote
1answer
38 views

Lower bound for $\text{ord}_{pq} a$

Let $p$ and $q$ be distinct odd prime numbers and $\gcd(a, pq)=1$. Is there an expression for lower bound of order of $a$ modulo $pq$? I know that with the given conditions we have$$a^{\text{lcm}(p-1,...
4
votes
3answers
101 views

There are many numeral systems. Why do we only use the $0-9$ Hindu-Arabic numeral system?

Here is a list of other systems: Babylonian numerals Egyptian numerals Aegean numerals May numerals Chinese numerals These system are far older than the current system. How did it get to be known ...
4
votes
1answer
52 views

A topology on the natural numbers

Is there a name of or a reference to the following topology on $X=\mathbb N$: $A\subseteq X$ is closed if and only if $n\in A\wedge m|n\implies m\in A$?
1
vote
4answers
48 views

Prove that $\forall k = m^2 + 1. \space m \in \mathbb{Z}^+$, if $k$ is divisible by any prime then that prime is congruent to $1, 2 \pmod 4$.

Prove that $\forall k = m^2 + 1. \space m \in \mathbb{Z}^+$, if $k$ is divisible by any prime then that prime is congruent to $1, 2 \pmod 4$. I am unable to realize why it can't have $2$ prime ...