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

learn more… | top users | synonyms

2
votes
1answer
73 views

Highest $n$ such that $2^n|a^{2012}+a^{2013}+a^{2014}+\cdots +a^{3012}$,$a=4k+2$

A question from BdMO 2013 Nationals: Let $a$ be an integer divisible by 2 but not divisible by 4. What is the largest positive integer n such that ...
1
vote
1answer
39 views

Fermat's little theorem and congruence classes

I don't understand how to use Fermat's little theorem to find remainders e.g if we are asked to find remainder of $50^{50}$ on division by $13$, what is a and what is $p$ in the formula? Also I ...
0
votes
1answer
28 views

Using Fermat's little theorem to find remainders. [duplicate]

I don't understand how to use Fermat's little theorem to find remainders e.g if we are asked to find remainder of 50^50 on division by 13, what is a and what is p in the formula? What is going on?? ...
3
votes
0answers
92 views

diophantine equation $ |x^2-py^2|=\frac{p-1}{2} $

Prime $p\equiv3\pmod4$, then diophantine equation $$ |x^2-py^2|=\frac{p-1}{2} $$ has a solution in integers en, $x^2-py^2=-1$ has no solution in integers. I'd be grateful for any help you are ...
4
votes
2answers
57 views

Squares modulo 2^n

How many squares are there modulo $2^n$? If we would deal with $p^n$, where p an odd prime, then we could use Hensel's Lemma, which clearly doesn't work with $2^n$.
0
votes
1answer
31 views

7-adic series expansion of square root of 2

Given the sequence $\{ a_n\}$ defined by the (positive and $a_n < 7^n$) solutions of the congruence $x^2 \equiv 2 \mod 7^n$ and $a_{n+1}\equiv a_n \mod 7^n$. e.g. the first one is $a_1 =3$ the ...
0
votes
0answers
6 views

Schemmel Totient Functions in Literature

I know how to prove that the Schemmel Totient functions are multiplicative, but I was wondering if someone could give me a reference to a place in the literature where such a proof is given.
1
vote
0answers
20 views

The logarithm of a product

Let $p$ be a prime number, $C\in \mathbb{N}$ and C is not a square. Then define $$F=\prod_{|z| \leq \sqrt{\frac{x}{2}} \atop |y|\leq \sqrt{\frac{x}{2}p}}{|z^2-Cy^2|}.$$ Note that we omit the term with ...
0
votes
1answer
14 views

Let a, b, and m be positive integers such that $(a,m) = (b,m) = 1$. Assume that $(ord_m(a), ord_m(b)) = 1$ Prove that $ord_m(ab) = ord_m(a)*ord_m(b) $

So I got $(ab)^{ord_m(a)*ord_m(b)} = 1 \bmod m$ so $ord_m(ab) \mid ord_m(a) * ord_m(b)$ I am stuck on how to proceed from here though
0
votes
2answers
29 views

Numbers in a list which are perfect squares and perfect cubes of numbers

How many numbers in the list $$1,2,3,...,2001$$ are perfect squares and perfect cubes of whole numbers? My progress: Well I do know $$1,4,9,16,25,36,...$$ are perfect squares and $$1,8,27,64,...$$ ...
1
vote
3answers
34 views

prove that if $a$ is not a unit in $\mathbb Z$/m$\mathbb Z$ then $a$ is a zero divisor in $\mathbb Z$/m$\mathbb Z$?

Ho can I prove that if $a$ is not a unit in $\mathbb Z$/m$\mathbb Z$ then $a$ is a zero divisor in $\mathbb Z$/m$\mathbb Z$ ? I am stuck on this problem I would appreciate a lot your help thanks!!
1
vote
3answers
153 views

Number of solutions for $\frac{1}{X} + \frac{1}{Y} = \frac{1}{N!}$ where $1 \leq N \leq 10^6$

Note: this is a programming challenge at this site For this equation $$\frac{1}{X} + \frac{1}{Y} = \frac{1}{N!}\quad ( N \text{ factorial} ),$$ find the number of positive integral solutions for ...
0
votes
2answers
18 views

Perfect Square and Multiple question

The population of a village is a perfect square. Later, with an increase of 100, the population was 1 more than a perfect square. Now with an additional increase of 100, the population is a perfect ...
2
votes
2answers
26 views

Prove that every positive integer $n$ has a unique expression of the form: $2^{r}m$ where $r\ge 0$ and $m$ is an odd positive integer

Prove that every positive integer $n$ has a unique expression of the form: $2^{r}m$ where $r\ge 0$ and $m$ is an odd positive integer if $n$ is odd then $n=2^{0}n$, but I dont know what to do when ...
10
votes
4answers
4k views
+50

How to use the Extended Euclidean Algorithm manually?

I've only found a recursive algorithm of the extended Euclidean algorithm. I'd like to know how to use it by hand. Any idea?
0
votes
1answer
27 views

Digit reversal arithmetic

How many three-digit odd numbers become bigger when their digits are reversed? $$abc<cba$$ and $c$ is either 1,3,5,7,9. This is the furthest I managed to reach.
1
vote
2answers
53 views

Three-Digit numbers divisbile by 3

How many three digit numbers are divisible by 3 and have an additional property that the sum of of their digits is 4 times the middle digit? My approach: let the number be $abc$ so $$abc \equiv ...
11
votes
5answers
202 views
+200

What are the applications of continued fractions?

What is the most motivating way to introduce continued fractions? Are there any real life applications of continued fractions?
3
votes
2answers
42 views

Conjecture on twin primes

Let $p$ and $p+2$ be both prime. I conjectured (with my ignorance) that $$p^{\frac{p+1}{2}}\equiv -1\mod{(p+2)}$$ except for $p=17,41,71,137, 191, 239....$ I verified this on Mathematica. So for ...
0
votes
1answer
31 views

Help on a perfect square.

Consider a question, that xyxyxyxy cannot be a perfect square. How should i tackle this problem. All i use is it must be $0,1 ($mod $3,4)$ and then the math, are there any another beatiful ways ...
0
votes
3answers
26 views

Division with remainder (Pos/Neg & Neg/Pos)

I guess it is a elementary school question, however I could not be sure: What are the remainders when: $-8$ is divided by $3$ $8$ is divided by $-3$ According to: $0<r<n$ where $m=qn+r$ ...
1
vote
0answers
25 views

Good introduction to number theory that develops and/or makes heavy use of commutative ring theory and lattice theory?

I'd like to learn some number theory, since it provides a lot of motivation for commutative ring theory and even some motivation for lattice theory (at least, that's the impression I'm under). ...
-5
votes
0answers
37 views

Integer solutions to the equation (1/x)+(1/y)=1/N! [on hold]

I am trying to find the number of positive integral solutions $(x,y)$ to the equation: $$\frac 1x + \frac 1y = \frac 1{N!}$$ where $N$ is a positive integer.
1
vote
1answer
26 views

Last two digit of number raised to exponents. [duplicate]

Find the last two digits of $3^{3^{2014}}$. Attempt: First I try to work with $3^{2014}$. So we can work on $\text{mod 10}$. Then, $$\begin{align}&3^1 \equiv 3\pmod{10}\\ &3^2 \equiv 9 ...
-1
votes
0answers
42 views

Prove something is divisible by a prime [on hold]

Let $p$ be a prime. Prove that $\sum_{k=j}^{p-1} \frac{k!}{ j! (k-j)! }$ is divisible by $p$ $\forall$ $j \in \{0, ..., p-2\}$. Where this problem comes from: I am trying to prove that ...
-3
votes
0answers
16 views

The integers mod sqrt{d} [on hold]

Show that $\mathbb{Z}[\sqrt{d}]$ has a unit which is neither $+1$ or $-1$. Conclude that $\mathbb{Z}[\sqrt{d}]$ has an infinite number of units.
0
votes
1answer
34 views

Using Fermat's Little theorem to prove that $12\mid n^2-1$ when $(n,6)=1$

I need help proving the first one via Fermat's little theorem. I need a hint, or a good starter!
0
votes
1answer
24 views

Median primes and cryptography

I've been considering something involving median numbers. If an integer is directly in the middle of two integers, is it possible to accurately extrapolate what two it is between? Can a prime be in ...
2
votes
2answers
70 views

How can you proof that the sum of three roots is irrational?

I would like to know how to proof that $\sqrt{2} + \sqrt{5} + \sqrt{7}$ is an irrational number. I know how to do the proof for a sum of to roots. Can I just define $\sqrt{2} + \sqrt{5} :=c$ and then ...
1
vote
2answers
42 views

Solving for a random number less than 401, generated by multiplying two numbers less than 21.

So, at a math meeting tonight we decided to play a game where you try to solve for a random number between 1 and 400 generated by multiplying two numbers between 1 and 20 together. Basically the ...
0
votes
0answers
13 views

Geographic representation of summations and floors

I am struggling to write this proof, and cannot figure out how to view this "geometrically:" Let $a$, $b\in\mathbb{N}$ be odd and relatively prime. Show that $$ ...
3
votes
0answers
31 views

Any rational as integer plus sum of $n$ reciprocals

Does there exist an integer $n$ with the following property? For any rational number $r$, there exist integers $a,b_1,\ldots,b_n$ such that $r=a+\sum_{i=1}^n\frac1{b_i}$.
1
vote
5answers
72 views

prove that $3$ does not divide $n^2+1$

How do I prove that $3$ does not divide $n^2+1$, for all $n\in\mathbb{Z}$, thought of in separate cases, but did not get, induction also was unable to ....
2
votes
2answers
69 views

Last digits, numbers

Can anyone please help me? 1) Find the last digit of $7^{12345}$ 2) Find the last 2 digits of $3^{3^{2014}}$. Attempt: 1) By just setting the powers of $7$ we have $7^1 = 7$, $7^2=49$, $7^3=343$, ...
3
votes
1answer
65 views

An easy question on number theory

Let $p$ be an odd prime. Is there any positive integer $k>1$ such that $p^k-1$ be a power of 2, that is $p^k-1=2^{\alpha}$ for some $\alpha\in \mathbb{N}$?
3
votes
2answers
64 views

Is this proof rigorus?

Simple abstract algebra proof: Suppose that $a,b,c\in\mathbb{Z}$ with $a$ and $b$ relatively prime. If $a|bc$, then $a|c$. Proof 1 Since $a$ & $b$ relatively prime, $a|bc\Rightarrow a|c$ ...
0
votes
3answers
33 views

mutliplicative inverse

Let a = 216, M = 342865. Show that gcd(a,M) = 1. Hence find the mutliplicative inverse, a^-1 mod M. I don't really know what to seach up for this question, but if anyone can provide me a example of ...
1
vote
1answer
37 views

Sum of Digit squares

I like to create problems for myself, While playing with my calculator, I found the following result. Take any positive digit $a_0$, and let $a_n$ denote the sum of digit squares of $a_{n-1}$. Then ...
4
votes
3answers
575 views

Proof about prime numbers

Can we prove that every prime larger than 3 gives a remainder of 1 or 5(edited) if divided by 6 and if so, which formulas can be used while proving?
3
votes
5answers
108 views

$\sqrt[3]{2}$ is not the root of a quadratic with rational coefficients?

How can one show that $\sqrt[3]{2}$ is not a root of a quadratic with rational coefficients? It is clear that if $\sqrt[3]{2}$ is the root of such a quadratic, then it is also the root of a quadratic ...
1
vote
0answers
32 views

Math Problem 10 - 9 x 8 - 7 x 6 - 5 x 4 - 3 x 2 - 2 x 1 = 1 [on hold]

Put {}, [] and () in the expression 10 - 9 x 8 - 7 x 6 - 5 x 4 - 3 x 2 - 2 x 1 = 1 in order to be true.
0
votes
1answer
27 views

Find $m$ such that $4 \nshortmid \phi(m)$

The above question is taken from Silvermans A Friendly Introduction to Number Theory, volume 3. Here's what I've got so far: I know that $$\phi(m) = \prod_{p|m} (p^{k-1})(p-1)$$ and I tried several ...
1
vote
0answers
20 views

Definition of Euler phi function

Why is $\phi(n)$ defined to be $$\phi(n) = |\{ 0 \le b < n \mid gcd(b,n) = 1 \}|$$ rather than $$\phi(n) = |\{ 0 < b < n \mid gcd(b,n) = 1 \}|$$ ? I realize it doesn't make a practical ...
1
vote
0answers
26 views

Almost perfect numbers

A positive integer $n$ is called almost perfect if the sum of its divisors smaller than $n$ is $n-1$. What are all almost perfect numbers $n$ such that some power $n^k$ is also almost perfect for at ...
3
votes
2answers
67 views

Existence of perfect square between the sum of the first $n$ and $n + 1$ prime numbers

Let $A_n$ be the sum of the first $n$ prime numbers. Prove that there is a perfect square between $A_n$ and $A_{n+1}$.
2
votes
1answer
42 views

How do i prove this is a metric?

Define a metric $d$ on $\mathbb{Z}$ in the following manner: $d(x,y)=\min\{\frac{1}{n!} : n! \text{ divides } x-y \text{ where } n\in\mathbb{Z}^+ \}$ if $x\neq y$. $d(x,x)=0$ ...
2
votes
3answers
67 views

Prove that $7^{100}+3^{10}=8^{100}$ or $7^{100}+3^{10}<8^{100}$ [on hold]

Prove that $7^{100}+3^{10}=8^{100}$ or $7^{100}+3^{10}<8^{100}$ I tried using some theorems of divisibility, to show that one divides the other, and the other also divides the first, but could ...
1
vote
3answers
24 views

Number of quadractic residues $\mod p$ and $\mod n$.

Let $p$ be an odd prime. Then among the integers $\{1,2,3,\cdots,p-1\}$ exactly half are quadratic residues modulo $p$. I believe the above proposition. Let $n$ be an odd, square free ...
0
votes
0answers
36 views

Find all the primes $p$ for which $x^2\equiv13\pmod p$ has a solution.

I found that for $p=3$, we have $x^2\equiv2^2\equiv4\equiv13\pmod 3\equiv-9\equiv0\pmod 3$. But how do I find out all the primes such that this holds?
2
votes
0answers
25 views

Question on Fermat Numbers Factorization

Let $F_{n}=2^{2^n}+1$ be a Fermat number. A classic idea using orders and Fermat's Little Theorem shows that a prime divisor $p$ of $F_{n}$ must be of the form $p=k .2^{n+1}+1$. Furthermore, using the ...